HDU 2852(KiKi's K-Number)

spoiler posted @ 2011年4月11日 22:43 in ACM经典题目之线段树 , 1019 阅读
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define max 100000
#define lowbit(x) (x&(-x))
using namespace std;
const int N=100001;
int c[100005],a[100005];

int getsum(int x){
	int sum=0;
	while(x){
		sum+=c[x];
		x-=lowbit(x);
	}
	return sum;
}

int modify(int x,int num){
	while(x<=N){
		c[x]+=num;
		x+=lowbit(x);
	}
	return 0;
}

int main(){
	int n,i,left,right,md;
	int sign,m,t,num1;
	while(scanf("%d",&n)!=EOF){
		memset(c,0,sizeof(c));
		memset(a,0,sizeof(a));
		while(n--){
			scanf("%d",&sign);
			if(sign==0){
				scanf("%d",&t);
				a[t]++;
				modify(t,1);
			}
			else if(sign==1){
				scanf("%d",&t);
				if(!a[t])
					cout<<"No Elment!"<<endl;
				else{
					a[t]--;
					modify(t,-1);
				}
			}
			else if(sign==2){
				scanf("%d %d",&m,&t);
				num1=getsum(m)+t;
				if(num1>getsum(max)){
					cout<<"Not Find!"<<endl;
				        continue;				
				}
				left=m+1;
				right=max;
				while(right-left>1){
					md=getsum((right+left)/2);
					if(md>num1){
						right=(right+left)/2;
					}
					else if(md<num1){
						left=(right+left)/2;
					}
					else {
						if(a[(right+left)/2]){
							cout<<(right+left)/2<<endl;
							break;
						}
						else
							right=(right+left)/2;
					}
				}
				if(right-left<=1){
					if(getsum(left)>=num1)
						cout<<left<<endl;
					else
						cout<<right<<endl;
				}
			}
			
		}
	}
	return 0;
}

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter