- //by Judge
- #include<iostream>
- #include<cstdio>
- using namespace std;
- const int M=1e5+111;
- #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
- char buf[1<<21],*p1=buf,*p2=buf;
- inline int read(){
- #define num ch-'0'
- char ch;bool flag=0;int res;
- while(!isdigit(ch=getc()))
- (ch=='-')&&(flag=true);
- for(res=num;isdigit(ch=getc());res=res*10+num);
- (flag)&&(res=-res);
- #undef num
- return res;
- }
- char sr[1<<21],z[20];int C=-1,Z;
- inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}
- inline void print(int x){
- if(C>1<<20)Ot();if(x<0)sr[++C]=45,x=-x;
- while(z[++Z]=x%10+48,x/=10);
- while(sr[++C]=z[Z],--Z);sr[++C]='\n';
- }
- int n,cnt,root;
- int Rand() {
- static int seed=703;
- return seed=int(seed*48271LL%(~0u>>1));
- }
- struct Node {
- int val,key,siz,ch[2];
- void clear() {
- ch[0]=ch[1]=siz=val=key=0;
- }
- } t[M];
- int update(int now){
- t[now].siz=t[t[now].ch[0]].siz+t[t[now].ch[1]].siz+1;
- }
- int merge(int u,int v) {
- if(!u || !v) return u|v;
- if(t[u].key<t[v].key) {
- t[u].ch[1]=merge(t[u].ch[1],v);
- update(u); return u;
- } else {
- t[v].ch[0]=merge(u,t[v].ch[0]);
- update(v); return v;
- }
- }
- void split_val(int now,int k,int& x,int& y) {
- if(!now) return (void)(x=y=0);
- if(t[now].val<=k)
- x=now,split_val(t[now].ch[1],k,t[now].ch[1],y);
- else
- y=now,split_val(t[now].ch[0],k,x,t[now].ch[0]);
- update(now);
- }
- void split_k(int now,int k,int& x,int& y) {
- if(!now) return (void)(x=y=0);
- update(now);
- if(t[t[now].ch[0]].siz<k)
- x=now,split_k(t[now].ch[1],k-t[t[now].ch[0]].siz-1,t[now].ch[1],y);
- else
- y=now,split_k(t[now].ch[0],k,x,t[now].ch[0]);
- update(now);
- }
- void ins(int x) {
- int u,a,b;
- t[u=++cnt].key=Rand();
- t[u].val=x,t[u].siz=1;
- split_val(root,x,a,b);
- root=merge(merge(a,u),b);
- }
- void del(int x) {
- int a,b,c,d;
- split_val(root,x-1,a,b);
- split_k(b,1,c,d);
- t[c].clear(),root=merge(a,d);
- }
- int get_rank(int x) {
- int a,b,c;
- split_val(root,x-1,a,b);
- c=t[a].siz+1;
- root=merge(a,b);
- return c;
- }
- int get_val(int& now,int x) {
- int a,b,c,d,e;
- split_k(now,x-1,a,b);
- split_k(b,1,c,d);
- e=t[c].val;
- now=merge(a,merge(c,d));
- return e;
- }
- int pre(int x) {
- int a,b,c;
- split_val(root,x-1,a,b);
- c=get_val(a,t[a].siz);
- root=merge(a,b);
- return c;
- }
- int sub(int x) {
- int a,b,c;
- split_val(root,x,a,b);
- c=get_val(b,1);
- root=merge(a,b);
- return c;
- }
- int main() {
- n=read(); int opt,x;
- while(n--){
- opt=read(),x=read();
- switch(opt){
- case 1: ins(x); break;
- case 2: del(x); break;
- case 3: print(get_rank(x)); break;
- case 4: print(get_val(root,x)); break;
- case 5: print(pre(x)); break;
- case 6: print(sub(x)); break;
- }
- } Ot(); return 0;
- }
来源: https://www.cnblogs.com/Judge/p/9506980.html