%%%
by Jr_Zlw @ 2021-02-17 14:36:42
加快读鸭
by Jr_Zlw @ 2021-02-17 14:37:51
@[醉水](/user/150611) 呐,A了(您没有用随机key值诶)
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,minn,rot=0,tot=0,sum=0;
struct node{
int val,siz,tag,l,r,key;
}a[100001];
inline int read()
{
int res=0;bool flag=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')flag=1;ch=getchar();}
while(ch>='0'&&ch<='9')res=(res<<1)+(res<<3)+(ch^48),ch=getchar();
return flag?-res:res;
}
int newnode(int x){tot++;a[tot].val=x;a[tot].siz=1;a[tot].key=rand();return tot;}
void pushup(int x){a[x].siz=a[a[x].l].siz+a[a[x].r].siz+1;}
void pushdown(int x){a[x].val+=a[x].tag;a[a[x].l].tag+=a[x].tag;a[a[x].r].tag+=a[x].tag;a[x].tag=0;}
int merge(int x,int y)
{
if(!x||!y) return x+y;
//if(rand()%(a[x].siz+a[y].siz)<=a[x].siz)
if(a[y].key<=a[x].key)
{
pushdown(x);
a[x].r=merge(a[x].r,y);
pushup(x);
return x;
}
else{
pushdown(y);
a[y].l=merge(x,a[y].l);
pushup(y);
return y;
}
}
void split(int now,int k,int &atl,int &atr){
if(!now){
atl=atr=0;
return;
}
pushdown(now);
if(a[now].val<=k) split(a[now].r,k,a[atl=now].r,atr);
else split(a[now].l,k,atl,a[atr=now].l);
pushup(now);
}
int kth(int k){
int now=rot;
pushdown(now);
while(a[a[now].l].siz+1!=k){
if(a[a[now].l].siz<k) k-=(a[a[now].l].siz+1),now=a[now].r;
else now=a[now].l;
pushdown(now);
}
return a[now].val;
}
void print(int now){
if(!now) return;
print(a[now].l);
printf("%d %d",a[now].val,a[now].tag);puts("");
print(a[now].r);
}
int main()
{
srand(time(0));
int x,y,z;
char kind;int k;
n=read();minn=read();
for(int i=1;i<=n;i++)
{
scanf("%s",&kind);k=read();
if(kind=='I'){
if(k<minn) continue;
split(rot,k,x,y);
rot=merge(merge(x,newnode(k)),y);
}
else if(kind=='A'){
// split(rot,minn-k-1,x,rot);
// sum+=a[x].siz;
a[rot].tag+=k;
}
else if(kind=='S'){
split(rot,minn+k-1,x,rot);
sum+=a[x].siz;
a[rot].tag-=k;
}
else{
k=a[rot].siz-k+1;
// cout<<a[rot].siz<<" "<<k;
if(k<1||a[rot].siz<k) puts("-1");
else printf("%d",kth(k)),puts("");
}
// print(rot);puts("");
}
printf("%d",sum);
}
```
by Jr_Zlw @ 2021-02-17 22:44:12
(看merge中的第二句
by Jr_Zlw @ 2021-02-17 22:45:06
比我还快(小声bb
by Jr_Zlw @ 2021-02-17 22:47:19
@[Jr_zLiwen](/user/191281) %%%谢谢大佬
by mrozhx @ 2021-02-18 16:24:18