【数据结构】树状数组

在线求第k大数/中位数
树状数组+二分 nlognlogn
KiKi’s K-Number

#include<iostream>
using namespace std;const int N=100010;
int tr[N];
int m;int lowbit(int x){return x&(-x);}
int query(int x){int res=0;for(int i=x;i>0;i-=lowbit(i)){res+=tr[i];}return res;
}
void add(int x,int k){for(int i=x;i<N;i+=lowbit(i)){tr[i]+=k;}
}bool check(int mid,int k){int k1=query(mid);if(k1>=k)return 1;return 0;
}int main(){std::ios::sync_with_stdio(false);
int m;while(cin>>m){for(int i=0;i<N;i++)tr[i]=0;while (m--){int op;cin>>op;if(op==0){int e;cin>>e;add(e,1);}else if(op==1){int e;cin>>e;int k1=query(e-1);int k2=query(e);if(k1==k2){cout<<"No Elment!\n";}else add(e,-1);}else {int a,k;cin>>a>>k;int k1=query(a);k+=k1;int l=0;int r=100010;while (l<r){int mid=(l+r)>>1;if(check(mid,k))r=mid;else l=mid+1;}if(l==0||r==100010)cout<<"Not Find!\n";else cout<<l<<"\n";}}}}