| 123456 |
- #include <cstdint>
- #include <iostream>
- #include <random>
- #include <vector>
- using namespace std;struct Node{int l=0,r=0,size=0,key=0,id=0;uint32_t priority=0;};
- int main(){ios::sync_with_stdio(false);cin.tie(nullptr);mt19937 rng(923847);vector<Node>tr(1);auto pull=[&](int x){tr[x].size=tr[tr[x].l].size+tr[tr[x].r].size+1;};auto split=[&](auto&&self,int root,int key)->pair<int,int>{if(!root)return{0,0};if(tr[root].key<=key){auto[a,b]=self(self,tr[root].r,key);tr[root].r=a;pull(root);return{root,b};}auto[a,b]=self(self,tr[root].l,key);tr[root].l=b;pull(root);return{a,root};};auto merge=[&](auto&&self,int a,int b)->int{if(!a||!b)return a?a:b;if(tr[a].priority<tr[b].priority){tr[a].r=self(self,tr[a].r,b);pull(a);return a;}tr[b].l=self(self,a,tr[b].l);pull(b);return b;};int root=0,op;while(cin>>op&&op){if(op==1){int id,key;cin>>id>>key;int z=tr.size();tr.push_back({0,0,1,key,id,static_cast<uint32_t>(rng())});auto[a,b]=split(split,root,key);root=merge(merge,merge(merge,a,z),b);}else{if(!root){cout<<0<<'\n';continue;}int z=root;if(op==2)while(tr[z].r)z=tr[z].r;else while(tr[z].l)z=tr[z].l;cout<<tr[z].id<<'\n';auto[a,b]=split(split,root,tr[z].key-1);auto[c,d]=split(split,b,tr[z].key);root=merge(merge,a,merge(merge,merge(merge,tr[c].l,tr[c].r),d));}}}
|
