KiKi's K-Number
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3966 Accepted Submission(s): 1758
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?
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.
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
6
Not Find!
2
2
4
Not Find!
一个空的容器,进行三种操作:
0 a : 把a加进容器里;
1 a : 把a从容器中删除,如果没有a则输出No Elment!,如果有多个a则只删除一个;
2 a k : 求整个容器中所有比a大的数中的第k大的数,并输出,如果没有则输出NO Finds!。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <stack>
#include <queue>
#include <cmath>
#include <map>
#define ll __int64
#define mod 1000000007
#define dazhi 2147483647
const int N=;
using namespace std;
struct chairmantree
{
int rt[*N],ls[*N],rs[*N],sum[*N];
int tot;
void init()
{
tot=;
}
void build(int l,int r,int &pos)
{
pos=++tot;
sum[pos]=;
if(l==r) return ;
int mid=(l+r)>>;
build(l,mid,ls[pos]);
build(mid+,r,rs[pos]);
}
void update(int p,int c,int l,int r,int pre,int &pos)
{
pos=++tot;
ls[pos]=ls[pre];
rs[pos]=rs[pre];
sum[pos]=sum[pre]+c;
if(l==r) return ;
int mid=(l+r)>>;
if(p<=mid)
update(p,c,l,mid,ls[pre],ls[pos]);
else
update(p,c,mid+,r,rs[pre],rs[pos]);
}
int rank(int s,int e,int l,int r,int L,int R)
{
if(s<=l&&e>=r) return sum[R]-sum[L];
int ans=;
int mid=(l+r)>>;
if(s<=mid)
ans+=rank(s,e,l,mid,ls[L],ls[R]);
if(e>mid)
ans+=rank(s,e,mid+,r,rs[L],rs[R]);
return ans;
}
int query(int L,int R,int l,int r,int k)
{
if(l==r) return l;
int mid=(l+r)>>;
int x=sum[ls[R]]-sum[ls[L]];
if(k<=x)
query(ls[L],ls[R],l,mid,k);
else
query(rs[L],rs[R],mid+,r,k-x);
}
} tree;
int m;
int exm;
int e;
int main()
{
int rr=;
while(scanf("%d",&m)!=EOF)
{
tree.init();
tree.build(,rr,tree.rt[]);
for(int i=; i<=m; i++)
{
scanf("%d",&exm);
if(exm==)
{
scanf("%d",&e);
tree.update(e,,,rr,tree.rt[i-],tree.rt[i]);
}
if(exm==)
{
scanf("%d",&e);
if(tree.rank(e,e,,rr,tree.rs[],tree.rt[i-]))
{
tree.update(e,-,,rr,tree.rt[i-],tree.rt[i]);
}
else
{
tree.update(e,,,rr,tree.rt[i-],tree.rt[i]);
printf("No Elment!\n");
}
}
if(exm==)
{
int a,k;
scanf("%d %d",&a,&k);
tree.update(,,,rr,tree.rt[i-],tree.rt[i]);
int q=tree.rank(,a,,rr,tree.rt[],tree.rt[i]);
int xx=tree.rank(,rr,,rr,tree.rt[],tree.rt[i]);
k+=q;
if(k>xx)
printf("Not Find!\n");
else
printf("%d\n",tree.query(tree.rt[],tree.rt[i],,rr,k));
}
}
}
return ;
}