首页 > ACM题库 > HDU-杭电 > HDU 2852-KiKi’s K-Number-线段树-[解题报告]HOJ
2014
02-17

HDU 2852-KiKi’s K-Number-线段树-[解题报告]HOJ

KiKi’s K-Number

问题描述 :

For the k-th number, we all should be very familiar with it. Of course,to kiki it is also simple. Now Kiki meets a very similar problem, kiki wants to design a container, the container is to support the three operations.

Push: Push a given element e to container

Pop: Pop element of a given e from container

Query: Given two elements a and k, query the kth larger number which greater than a in container;

Although Kiki is very intelligent, she can not think of how to do it, can you help her to solve this problem?

输入:

Input some groups of test data ,each test data the first number is an integer m (1 <= m <100000), means that the number of operation to do. The next m lines, each line will be an integer p at the beginning, p which has three values:
If p is 0, then there will be an integer e (0 <e <100000), means press element e into Container.

If p is 1, then there will be an integer e (0 <e <100000), indicated that delete the element e from the container  

If p is 2, then there will be two integers a and k (0 <a <100000, 0 <k <10000),means the inquiries, the element is greater than a, and the k-th larger number.

输出:

Input some groups of test data ,each test data the first number is an integer m (1 <= m <100000), means that the number of operation to do. The next m lines, each line will be an integer p at the beginning, p which has three values:
If p is 0, then there will be an integer e (0 <e <100000), means press element e into Container.

If p is 1, then there will be an integer e (0 <e <100000), indicated that delete the element e from the container  

If p is 2, then there will be two integers a and k (0 <a <100000, 0 <k <10000),means the inquiries, the element is greater than a, and the k-th larger number.

样例输入:

5
0 5
1 2
0 6
2 3 2
2 8 1
7
0 2
0 2
0 4
2 1 1
2 1 2
2 1 3
2 1 4

样例输出:

No Elment!
6
Not Find!
2
2
4
Not Find!

/*
题意:
三种操作
0 x:向容器里加入x;
1 x: 在容器内删除x,不存在x则输出“No Elment”
2 x y:在容器中找到大于x的第y个数,没有则输出“Not Find”
题解: 树状数组
操作1:直接add(x,1)
操作2:查找sum(x)和sum(x-1),差值为0则不存在x,反之,add(x,-1)即可删除一个x
操作3:首先查找小于等于x的个数s,则找到大于x的第y个数相当于找到第s+y小数
*/
#include<stdlib.h>
#include<algorithm>
#include<iostream>
#include<string.h>
#include<cstdio>
using namespace std ;

const int maxn = 100005 ;

struct bit{
     int c[maxn] ; 
     void init(){
          memset(c , 0 ,sizeof(c));
     }
     int lowbit(int x){
         return x&(-x);
     }
     void add(int x ,int d){ //在x处加上d
          for( ; x < maxn ; x+=lowbit(x)) c[x]+=d ; 
     }
     int sum(int x){ //求小于等于x的个数
          int ans = 0 ;
          for( ; x>0 ; x-=lowbit(x))  ans +=c[x] ; 
          return ans ;
     }
     int getkth1(int k){// 求第K小数模版1
          int ans = 0 , cnt = 0 , i ;
          for(i = 20 ; i>=0 ; --i){
                ans += 1<<i ;
                if(ans>=maxn||cnt+c[ans]>=k) ans-=1<<i ;
                else cnt +=c[ans] ;      
          }
          return ans+1 ; 
     }
	 
		int getkth2(int k){//求第K小数模版2
			int l=0,r=maxn,mid,f;
			while(l<r-1)
			{ mid=(l+r)>>1;
			  f=sum(mid);
				if(f>=k) r=mid;
				else l=mid;
			}
			return r;
		}
};

int main()
{
	bit my;
	int op,m,x,y;
	while(scanf("%d",&m)!=EOF)
	{
		my.init();
		while(m--)
		{
			scanf("%d%d",&op,&x);
			if(op==0)
			{
				my.add(x,1);
			}
			else if(op==1)
			{
				if(my.sum(x)-my.sum(x-1)==0)
				puts("No Elment!");
				else 
				my.add(x,-1);
			}
			else 
			{
				scanf("%d",&y);
				if(my.sum(maxn-1)-my.sum(x)<y)
				puts("Not Find!");
				else 
				{
					printf("%d\n",my.getkth2(y+my.sum(x)));
				}
			}
		}
	}
    return 0 ;
}
/*
c++提交能过,g++就tle了,郁闷
*/
#include <cstdio>
#include <iostream>
#include <memory.h>
#include<queue>
#include<set>
#include<ctime>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
const int N=100001;
struct Tree
{
	int L,R,V;
	int lazy;
}tree[3*N];
void create(int t,int L,int R)
{
	int mid=(L+R)>>1;
	int l=2*t;
	int r=2*t+1;
	tree[t].L=L;
	tree[t].R=R;
	tree[t].V=0;
	tree[t].lazy=0;
	if(L<R)
	{
		create(l,L,mid);
		create(r,mid+1,R);
	}
}
void down(int t)
{
	int l=2*t;
	int r=2*t+1;
	if(tree[t].lazy==0)return ;
	if(tree[t].L<tree[t].R)
	{
	tree[l].V+=tree[t].lazy;
	tree[r].V+=tree[t].lazy;
	tree[l].lazy+=tree[t].lazy;
	tree[r].lazy+=tree[t].lazy;
	}
	tree[t].lazy=0;
}
void insert(int t,int L,int R,int v)
{
	int l=2*t;
	int r=2*t+1;
	int mid=(tree[t].L+tree[t].R)>>1;
	if(tree[t].L==L&&tree[t].R==R)
	{
		tree[t].V+=v;
		if(L<R)
		tree[t].lazy+=v;
		return ;
	}
	down(t);
	if(L>mid)insert(r,L,R,v);
	else if(R<=mid)insert(l,L,R,v);
	else 
	{
		insert(l,L,mid,v);
		insert(r,mid+1,R,v);
	}
}
int query(int t,int L)
{
	int l=2*t;
	int r=2*t+1;
	int mid=(tree[t].L+tree[t].R)>>1;
	if(tree[t].L==tree[t].R)
	return tree[t].V;
	down(t);
	if(L<=mid)return query(l,L);
	else return query(r,L);
}
int get(int k)
{
	int l=0,r=N,mid;
	while(l<r-1)
	{
		mid=(l+r)>>1;
		int t=query(1,mid);
		if(t>=k)
		r=mid;
		else 
		l=mid;
	}
	return l;
}

int main()
{
	int op,k,n,y;
	while(scanf("%d",&n)!=EOF)
	{
		
		create(1,1,N+1);
		while(n--)
		{
			scanf("%d%d",&op,&k);
			if(op==0)
			{
				insert(1,k+1,N,1);
			}
			else if(op==1)
			{
				if(query(1,k+1)-query(1,k)==0)
				puts("No Elment!");
				else 
				insert(1,k+1,N,-1);
			}
			else if(op==2)
			{
				scanf("%d",&y);
				int s=query(1,k+1);
				int ans=get(y+s);
				if(ans==N-1)
				puts("Not Find!");
				else 
				printf("%d\n",ans);
			}
		}
	}
}

解题参考:http://blog.csdn.net/wsniyufang/article/details/6733431