会了FHQ，treap什么的就忘了吧……
#includeusing namespace std; struct FHQ { int v,w,size,l,r; }t[300005]; int root,k,n,_min,tot,add,x,y,ans,cnt; char ch; int newnode(int k) { ++tot; if(!root)root=1; t[tot].size=1,t[tot].v=k,t[tot].w=rand(); return tot; } void update(int now) { t[now].size=t[t[now].l].size+t[t[now].r].size+1; } int merge(int x,int y) { if(!x||!y)return x+y; if(t[x].w<t[y].w) { t[x].r=merge(t[x].r,y); update(x); return x; } else { t[y].l=merge(x,t[y].l); update(y); return y; } } void split(int now,int val,int &x,int &y) { if(!now){x=y=0;return;} if(t[now].v<val) { x=now; split(t[now].r,val,t[now].r,y); } else { y=now; split(t[now].l,val,x,t[now].l); } update(now); } void change(int now,int k) { if(!now)return; t[now].v+=k; change(t[now].l,k); change(t[now].r,k); } int find(int now,int k) { if(t[t[now].l].size==k-1)return now; if(t[t[now].l].size>k-1)return find(t[now].l,k); if(t[t[now].l].size 1)return find(t[now].r,k-t[t[now].l].size-1); } void pp() { cout< endl; for(int i=1;i2)<' '; cout<<endl; for(int i=1;i2)< ' '; cout<<endl; for(int i=1;i2)< [i].v' '; cout<<endl; for(int i=1;i2)< [i].l' '; cout<<endl; for(int i=1;i2)< [i].r' '; cout< [i].sizeendl; } int main() { srand(114514); cin>>n>>_min; for(int i=1;i) { cin>>ch; if(ch=='I') { cin>>k; if(k<_min>continue; split(root,k,x,y); root=merge(merge(x,newnode(k)),y); } if(ch=='A') { cin>>k; change(root,k); } if(ch=='S') { cin>>k; change(root,-k); split(root,_min,x,y); ans+=t[x].size; root=y; } if(ch=='F') { cin>>k; if(t[root].size<k) { cout<1<<endl; continue; } cout< 1)].v<<endl; } ///pp(); } cout<<ans; return 0; } [find(root,tot-ans-k+
Original: https://www.cnblogs.com/29taorz/p/15305384.html
Author: T_X蒻
Title: FHQtreap（我有个绝妙的理解方法，但课的时间不够[doge]）
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/584345/
转载文章受原作者版权保护。转载请注明原作者出处！