题目描述
操作:整体加/减 统计小于k的个数,并删除
fhq-treap
$O(nlogn)$
对于一个fhq-treap来说以上这几种操作都很简单,就是split和merge的简单结合详见代码
C++ 代码
#include<bits/stdc++.h>
using namespace std;
int n,low,delta;
const int maxn=1e5+5;
struct fhq_treap
{
int sz,l,r,v,rnd,cnt;
}tr[maxn];
int root,tot;
void pushup(int now)
{
tr[now].sz=tr[tr[now].l].sz+tr[tr[now].r].sz+tr[now].cnt;
}
int merge(int x,int y)
{
if(!x || !y) return x+y;
if(tr[x].rnd<=tr[y].rnd)
{
tr[x].r=merge(tr[x].r,y);
pushup(x);
return x;
}
else
{
tr[y].l=merge(x,tr[y].l);
pushup(y);
return y;
}
}
void split(int now,int k,int &x,int &y)
{
if(!now) x=0,y=0;
else
{
if(k>=tr[now].v)
{
x=now;
split(tr[now].r,k,tr[x].r,y);
}
else
{
y=now;
split(tr[now].l,k,x,tr[now].l);
}
pushup(now);
}
}
int del(int val)
{
int x,y;
split(root,val,x,y);
root=y;
return tr[x].sz;
}
int query(int k)
{
int x=root;
while(1)
{
if(k<=tr[tr[x].l].sz) x=tr[x].l;
else if(k==tr[tr[x].l].sz+1) return tr[x].v;
else k-=tr[tr[x].l].sz+1,x=tr[x].r;
}
return 0;
}
int newnode(int val)
{
tot++;
tr[tot].sz=tr[tot].cnt=1;
tr[tot].v=val; tr[tot].rnd=rand();
return tot;
}
void insert(int val)
{
int x,y;
split(root,val,x,y);
root=merge(x,merge(newnode(val),y));
}
int main()
{
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
scanf("%d%d",&n,&low);
int x,ans=0;
for(int i=1;i<=n;i++)
{
char op[2];
cin>>op;
scanf("%d",&x);
if(op[0]=='I')
{
if(x>=low)
{
x-=delta;
insert(x);
}
continue;
}
if(op[0]=='A')
{
delta+=x;
continue;
}
if(op[0]=='S')
{
delta-=x;
ans+=del(low-delta-1);
continue;
}
if(op[0]=='F')
{
int cnt=tr[root].sz;
if(x>cnt) printf("-1\n");
else printf("%d\n",query(cnt-x+1)+delta);
}
}
printf("%d\n",ans);
return 0;
}