| 1234 |
- #include <iostream>
- #include <vector>
- using namespace std;struct Node{int ch[2]{},parent=0,size=1,key=0;};
- int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int q;cin>>q;vector<Node>tr(q+1);int root=0,nodes=0;auto size=[&](int x){return x?tr[x].size:0;};auto pull=[&](int x){tr[x].size=size(tr[x].ch[0])+size(tr[x].ch[1])+1;};auto rotate=[&](int x){int y=tr[x].parent,z=tr[y].parent,d=tr[y].ch[1]==x,b=tr[x].ch[d^1];if(z)tr[z].ch[tr[z].ch[1]==y]=x;else root=x;tr[x].parent=z;tr[x].ch[d^1]=y;tr[y].parent=x;tr[y].ch[d]=b;if(b)tr[b].parent=y;pull(y);pull(x);};auto splay=[&](int x,int goal=0){while(tr[x].parent!=goal){int y=tr[x].parent,z=tr[y].parent;if(z!=goal)((tr[y].ch[1]==x)==(tr[z].ch[1]==y)?rotate(y):rotate(x));rotate(x);}if(!goal)root=x;};auto find=[&](int key){int u=root,last=0;while(u&&tr[u].key!=key){last=u;u=tr[u].ch[key>tr[u].key];}if(u)splay(u);else if(last)splay(last);return u;};auto insert=[&](int key){if(!root){root=++nodes;tr[root].key=key;return;}int u=root,p=0;while(u){p=u;if(tr[u].key==key){splay(u);return;}u=tr[u].ch[key>tr[u].key];}int x=++nodes;tr[x].key=key;tr[x].parent=p;tr[p].ch[key>tr[p].key]=x;splay(x);};auto erase=[&](int key){int x=find(key);if(!x||tr[x].key!=key)return;int L=tr[x].ch[0],R=tr[x].ch[1];if(L)tr[L].parent=0;if(R)tr[R].parent=0;if(!L){root=R;return;}root=L;int u=L;while(tr[u].ch[1])u=tr[u].ch[1];splay(u);tr[u].ch[1]=R;if(R)tr[R].parent=u;pull(u);};auto kth=[&](int k){if(k<1||k>size(root))return -1;int u=root;while(true){int left=size(tr[u].ch[0]);if(k==left+1){splay(u);return tr[u].key;}if(k<=left)u=tr[u].ch[0];else k-=left+1,u=tr[u].ch[1];}};auto less=[&](int key){int u=root,ans=0,last=0;while(u){last=u;if(tr[u].key<key)ans+=size(tr[u].ch[0])+1,u=tr[u].ch[1];else u=tr[u].ch[0];}if(last)splay(last);return ans;};while(q--){char op;int x;cin>>op>>x;if(op=='I')insert(x);else if(op=='D')erase(x);else if(op=='K'){int ans=kth(x);if(ans==-1)cout<<"invalid\n";else cout<<ans<<'\n';}else cout<<less(x)<<'\n';}}
|
