hdu2852 KiKi's K-Number 树状数组求第k大数

//再求第k大数时只需要getsum(b-1)<getsum(a)+k<=getsum(b) //b就是a的第k大数 //又gesum(b-1)<=getsum(b)则可以用二分查找来做 #include<iostream> #include<cstdio> #include<cstring> using namespace std; const int maxn=100010; int tree[maxn]; int lowbit(int i) { ? ? return (i&(-i)); } int getsum(int i) { ? ? int sum=0; ? ? while(i>0) ? ? { ? ? ? ? sum+=tree[i]; ? ? ? ? i-=lowbit(i); ? ? } ? ? return sum; } void update(int i,int dx) { ? ? while(i<maxn) ? ? { ? ? ? ? tree[i]+=dx; ? ? ? ? i+=lowbit(i); ? ? } } void find(int left,int right,int num) { ? ? while(left<=right) ? ? { ? ? ? ? //int middle=(left+right)/2; ? ? ? ? int middle = left + (right - left) / 2; ? ? ? ? int tmp=getsum(middle); ? ? ? ? if(tmp<num) ? ? ? ? left=middle+1; ? ? ? ? else ? ? ? ? right=middle-1; ? ? } ? ? if(left>=maxn) ? ? printf("Not Find!n"); ? ? else? ? ? printf("%dn",left); } int main() { ? ? //freopen("in.txt","r",stdin); ? ?// freopen("out.txt","w",stdout); ? ? int m; ? ? while(scanf("%d",&m)!=EOF) ? ? { ? ? ? ? int p,a,k; ? ? ? ? memset(tree,sizeof(tree)); ? ? ? ? while(m--) ? ? ? ? { ? ? ? ? ? ? scanf("%d",&p); ? ? ? ? ? ? if(p==0) ? ? ? ? ? ? { ? ? ? ? ? ? ? ? scanf("%d",&a); ? ? ? ? ? ? ? ? update(a,1); ? ? ? ? ? ? } ? ? ? ? ? ? else if(p==1) ? ? ? ? ? ? { ? ? ? ? ? ? ? ? scanf("%d",&a); ? ? ? ? ? ? ? ? if(!(getsum(a)-getsum(a-1))) ? ? ? ? ? ? ? ? { ? ? ? ? ? ? ? ? ? ? printf("No Elment!n"); ? ? ? ? ? ? ? ? ? ? continue; ? ? ? ? ? ? ? ? } ? ? ? ? ? ? ? ? else ? ? ? ? ? ? ? ? update(a,-1); ? ? ? ? ? ? } ? ? ? ? ? ? else ? ? ? ? ? ? { ? ? ? ? ? ? ? ? scanf("%d%d",&a,&k); ? ? ? ? ? ? ? ? int tmp=getsum(a); ? ? ? ? ? ? ? ? find(a+1,maxn-1,tmp+k); ? ? ? ? ? ? } ? ? ? ? } ? ? } }