P1486 [NOI2004]郁闷的出纳员
皎月半洒花
2018-04-28 21:16:41
这个题算是平衡树系列的一个进阶版本了吧$qwq$.
好吧我承认，这个题我一开始做的时候已经想出了大约$60$%的样子，但是最后还是偷偷地瞅了眼题解，发现似乎很有道理，然后$A$了$emmmm$.
那么好像很显然，我们坑定不能一个一个地修改，区间修改由于每次都是$1$~$n$，所以并没有什么很大的意义。所以我们可以考虑引入一个标记，每次$A$就$$delta+=num$$每次$I$就$$insert(num-delta)$$，询问时就$$cout<<query+delta$$,再加上几个判断是不是非法操作。
$emmmmm$好像海星，到这一步大约已经可以够得着$NOIP$的思维难度了。然而这是一道省选题，所以这么搞还是捕星，因为删除操作和询问离职人员好像很难搞。
那么，在这里我们考虑将$-INF$和$INF$在一开始就插入平衡树里。每次$insert$操作$tot++$,最后只需要用$$tot-(find\_rank(INF)-2)$$就可以算出离职人数。
那么只剩下最后一个问题了——我们该怎么删除呢？这里就需要用到一个二叉搜索树里很精妙的操作了——删除根的子树。我们可以在执行$S$操作时先$delta-=num$，然后将$-INF$旋转到根节点，将$minn-delta$旋转到根节点的右儿子，然后删除根节点的右子树的左子树即可。
诶这个操作很熟悉啊，不也是区间翻转时的操作吗？
诶怎么旋转$minn-delta$啊？
我们可以很简单地插入删除，这很简单，但是为什么要以$minn-delta$作为所删除的单调区间的上界？这个地方你可以稍微意会一下……**因为我们插入的是$num-delta$啊!**
嗯，我还是太弱了。
# $\color{red}Code:$
```cpp
#include<iostream>
#include<cstdio>
using namespace std;
#define MAXN 1000000
#define INF 283653129
int f[MAXN],cnt[MAXN],value[MAXN],sons[MAXN][2],sub_size[MAXN],whole_size,root;
inline int qread(){
int res=0,k=1;
char c=getchar();
while(!isdigit(c)){
if(c=='-')k=-1;
c=getchar();
}
while(isdigit(c)){
res=(res<<1)+(res<<3)+c-48;
c=getchar();
}
return res*k;
}
inline void S_Clear(int x){
sons[x][0]=sons[x][1]=f[x]=sub_size[x]=cnt[x]=value[x]=0;
}
inline bool get_which(int x){
return sons[f[x]][1]==x;
}
inline void update(int x){
if (x){
sub_size[x]=cnt[x];
if (sons[x][0]) sub_size[x]+=sub_size[sons[x][0]];
if (sons[x][1]) sub_size[x]+=sub_size[sons[x][1]];
}
return ;
}
inline void rotate(int x){
int father=f[x],g_father=f[father],which_son=get_which(x);
sons[father][which_son]=sons[x][which_son^1];
f[sons[father][which_son]]=father;
sons[x][which_son^1]=father;
f[father]=x;
f[x]=g_father;
if(g_father){
sons[g_father][sons[g_father][1]==father]=x;
}
update(father);
update(x);
}
inline void splay(int x,int goal){
for(int qwq;(qwq=f[x])!=goal;rotate(x)){
if(f[qwq]!=goal){
rotate(get_which(x)==get_which(qwq)?qwq:x);
}
}
if(!goal){
root=x;
}
}
inline void insert(int x){
if(!root){
whole_size++;
sons[whole_size][0]=sons[whole_size][1]=f[whole_size]=0;
root=whole_size;
sub_size[whole_size]=cnt[whole_size]++;
value[whole_size]=x;
return ;
}
int now=root,fa=0;
while(1){
if(x==value[now]){
cnt[now]++;
update(now);
update(fa);
splay(now,0);
break;
}
fa=now;
now=sons[now][value[now]<x];
if(!now){
whole_size++;
sons[whole_size][0]=sons[whole_size][1]=0;
f[whole_size]=fa;
sub_size[whole_size]=cnt[whole_size]=1;
sons[fa][value[fa]<x]=whole_size;
value[whole_size]=x;
update(fa);
splay(whole_size,0);
break;
}
}
}
inline int find_num(int x){
int now=root;
while(1){
if(sons[now][0]&&x<=sub_size[sons[now][0]])
now=sons[now][0];
else {
int temp=(sons[now][0]?sub_size[sons[now][0]]:0)+cnt[now];
if(x<=temp)return value[now];
x-=temp;
now=sons[now][1];
}
}
}
inline int find_ID(int x){
int now=root;
while(1){
if(x==value[now]){
return now;
}
else now=sons[now][value[now]<x];
}
}
inline int find_rank(int x){
int now=root,ans=0;
while(1){
if (x<value[now])
now=sons[now][0];
else{
ans+=(sons[now][0]?sub_size[sons[now][0]]:0);
if (x==value[now]){
splay(now,0); return ans+1;
}
ans+=cnt[now];
now=sons[now][1];
}
}
}
inline int find_pre(){
int now=sons[root][0];
while(sons[now][1])now=sons[now][1];
return now;
}
inline int find_suffix(){
int now=sons[root][1];
while(sons[now][0])now=sons[now][0];
return now;
}
inline void my_delete(int x){
int hhh=find_rank(x);
if (cnt[root]>1){
cnt[root]--;
update(root);
return;
}
if (!sons[root][0]&&!sons[root][1]) {
S_Clear(root);
root=0;
return;
}
if (!sons[root][0]){
int old_root=root;
root=sons[root][1];
f[root]=0;
S_Clear(old_root);
return;
}
else if (!sons[root][1]){
int old_root=root;
root=sons[root][0];
f[root]=0;
S_Clear(old_root);
return;
}
int left_max=find_pre(),old_root=root;
splay(left_max,0);
sons[root][1]=sons[old_root][1];
f[sons[old_root][1]]=root;
S_Clear(old_root);
update(root);
}
int main(){
int m,num,minn;
char a;
cin>>m>>minn;
insert(-INF);
insert(INF);
int delta=0,sumtot=0;
for(int i=1;i<=m;i++){
cin>>a>>num;
switch(a){
case 'I' :{
if(num<minn)break;
insert(num-delta);
sumtot++;
break;
}
case 'A':{
delta+=num;
break;
}
case 'S':{
delta-=num;
insert(minn-delta);
int a=find_ID(-INF),b=find_ID(minn-delta);
splay(a,0);
splay(b,a);
sons[sons[root][1]][0]=0;
my_delete(minn-delta);
break;
}
case 'F':{
int sumnow=find_rank(INF)-2;
if(sumnow<num){
cout<<-1<<endl;
break;
}
int res=find_num(sumnow+2-num);
cout<<res+delta<<endl;
break;
}
}
}
int sumnow=find_rank(INF)-2;
cout<<sumtot-sumnow;
return 0;
}
```
代码好长啊……足足写了5.04K