P1486 [NOI2004] 郁闷的出纳员
有两种思路，均使用fhq-treap实现
- 维护一个变量delta表示全局偏移量，对于新插入的数减去偏移量。使用fhq-treap，可以分裂出<mid的部分，直接丢掉。
- 直接用fhq-treap维护一个类似于线段树的懒标记，每次放在根上即可。
方法1
#include<iostream>
#include<random>
using namespace std;
random_device rnd;
mt19937 rd(rnd());
const int N=100010;
unsigned pri[N];
int n,m,rt,l[N],r[N],v[N],sz[N],idx,ans,delta;
#define up(p) sz[p]=sz[l[p]]+sz[r[p]]+1;
int add(int x){
v[++idx]=x;
sz[idx]=1;
pri[idx]=rd();
return idx;
}
void split(int p,int &x,int &y,int k){
if(!p){
x=y=0;
return;
}
if(v[p]<=k){
x=p;
split(r[p],r[p],y,k);
}
else{
y=p;
split(l[p],x,l[p],k);
}
up(p);
}
int merge(int x,int y){
if(!x||!y)return x|y;
if(pri[x]>=pri[y]){
r[x]=merge(r[x],y);
up(x);
return x;
}
else{
l[y]=merge(x,l[y]);
up(y);
return y;
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
#endif
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;++i){
char x[3];
int a,b,k;
cin>>x>>k;
if(*x=='I'){
if(k<m)continue;
split(rt,a,b,k-1-delta);
rt=merge(merge(a,add(k-delta)),b);
}
else if(*x=='A')
delta+=k;
else if(*x=='F'){
if(k>sz[rt]){
cout<<"-1\n";
continue;
}
int p=rt;
while(p){
if(k<=sz[r[p]])p=r[p];
else if(k==sz[r[p]]+1){
cout<<v[p]+delta<<'\n';
break;
}
else k-=sz[r[p]]+1,p=l[p];
}
}
else{
delta-=k;
split(rt,a,b,m-1-delta);
rt=b;
ans+=sz[a];
}
}
cout<<ans;
return 0;
}
方法2
#include<iostream>
#include<random>
using namespace std;
random_device rnd;
mt19937 rd(rnd());
const int N=300010;
unsigned pri[N];
int n,m,rt,l[N],r[N],v[N],sz[N],idx,f[N],ans;
#define up(p) sz[p]=sz[l[p]]+sz[r[p]]+1;
int add(int x){
v[++idx]=x;
sz[idx]=1;
pri[idx]=rd();
return idx;
}
void ch(int p,int k){
v[p]+=k,f[p]+=k;
}
void down(int p){
int &k=f[p];
if(k)ch(l[p],k),ch(r[p],k),k=0;
}
void split(int p,int &x,int &y,int k){
if(!p){
x=y=0;
return;
}
down(p);
if(v[p]<=k){
x=p;
split(r[p],r[p],y,k);
}
else{
y=p;
split(l[p],x,l[p],k);
}
up(p);
}
int merge(int x,int y){
if(!x||!y)return x|y;
if(pri[x]>=pri[y]){
down(x);
r[x]=merge(r[x],y);
up(x);
return x;
}
else{
down(y);
l[y]=merge(x,l[y]);
up(y);
return y;
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
#endif
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;++i){
char x[2];
int a,b,k;
cin>>x>>k;
if(*x=='I'){
if(k<m)continue;
split(rt,a,b,k-1);
rt=merge(merge(a,add(k)),b);
}
else if(*x=='A')
ch(rt,k);
else if(*x=='F'){
if(k>sz[rt]){
cout<<"-1\n";
continue;
}
int p=rt;
while(p){
down(p);
if(k<=sz[r[p]])p=r[p];
else if(k==sz[r[p]]+1){
cout<<v[p]<<'\n';
break;
}
else k-=sz[r[p]]+1,p=l[p];
}
}
else{
ch(rt,-k);
split(rt,a,b,m-1);
rt=b;
ans+=sz[a];
}
}
cout<<ans;
return 0;
}