2014
02-17

# 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”

*/
#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)
{
}
else if(op==1)
{
if(my.sum(x)-my.sum(x-1)==0)
puts("No Elment!");
else
}
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);
}
}
}
}