YbtOJ 维护集合 题解
Description
你需要维护一个可重集，初始集合为空，支持 4 种操作：
- I k 向集合内插入元素 k。
- A k 将集合内所有元素加上 k。
- S k 将集合内所有元素减去 k。
- F k 查询集合内第 k 大。
你需要进行 n 次操作。
一开始给出一个下界 Minv，表示集合内的所有元素都必须大于等于 Minv，在任何时刻，小于 Minv 的所有元素会被立刻删除。
最后还要输出被删除的元素个数。
1leq n leq 3times 10^5,0leq Minvleq 10^9
Solution
考虑用 fhq Treap 维护该可重集。
对于操作一，只需要直接插入即可。
对于操作二、三，由于是对当前集合内所有元素统一操作，所以考虑记录一个全局变量 Sum，表示当前集合内所有元素实际大小应该加上 Sum。
那么每次操作一需要注意插入的值要减去 Sum。
查询第 k 大还是基本操作，只是最后要加上 Sum。
注意与 Minv 的判断即可。
Code
代码语言：javascript复制#include<bits/stdc .h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define LL long long
#define Cn const
#define CI Cn int&
#define gc getchar
#define D isdigit(c=gc())
#define pc(c) putchar((c))
#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
using namespace std;
namespace Debug{
Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f ;cerr<<'='<<x<<",";_debug(f 1,y...);}
Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
#define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
namespace FastIO{
Tp I void read(Ty& x){char c;int f=1;x=0;W(!D) f=c^'-'?1:-1;W(x=(x<<3) (x<<1) (c&15),D);x*=f;}
Ts I void read(Ty& x,Ar&... y){read(x),read(y...);}
Tp I void write(Ty x){x<0&&(pc('-'),x=-x,0),x<10?(pc(x '0'),0):(write(x/10),pc(x '0'),0);}
Tp I void writeln(Cn Ty& x){write(x),pc('n');}
}using namespace FastIO;
Cn int N=1e5 10;
int n,Minv,Sum,root,tot,x,y,Ans;
struct node{int ch[2],sz,val,rand_val;}tr[N];
I int New_Node(CI v){return tr[ tot]=(node){{0,0},1,v,rand()},tot;}
#define PU(x) (tr[x].sz=tr[tr[x].ch[0]].sz tr[tr[x].ch[1]].sz 1)
int Merge(int x,int y){
if(!x!y) return x y;
if(tr[x].rand_val<tr[y].rand_val){
tr[x].ch[1]=Merge(tr[x].ch[1],y);
PU(x);
return x;
}else{
tr[y].ch[0]=Merge(x,tr[y].ch[0]);
PU(y);
return y;
}
}
void Split(int now,int k,int &x,int &y){
if(!now) x=y=0;
else{
if(tr[now].val<=k) x=now,Split(tr[now].ch[1],k,tr[now].ch[1],y);
else y=now,Split(tr[now].ch[0],k,x,tr[now].ch[0]);
PU(now);
}
}
int Rank(int now,int k){
while(1){
if(k<=tr[tr[now].ch[0]].sz) now=tr[now].ch[0];
else{
if(k==tr[tr[now].ch[0]].sz 1) return now;
else{
k-=tr[tr[now].ch[0]].sz 1;
now=tr[now].ch[1];
}
}
}
}
int main(){
RI i,a;for(read(n,Minv),i=1;i<=n;i ){
string str;cin>>str;if(read(a),str=="I") a>=Minv&&(Split(root,a-Sum,x,y),root=Merge(Merge(x,New_Node(a-Sum)),y),0);
else if(str=="A") Sum =a;else if(str=="S") Sum-=a,Split(root,Minv-Sum-1,x,y),root=y,Ans =tr[x].sz;
else if(str=="F") writeln(tr[root].sz<a?-1:tr[Rank(root,tr[root].sz-a 1)].val Sum);
}return writeln(Ans),0;
}
