P1486

发表于 分类于
[NOI2004] 郁闷的出纳员

[NOI2004] 郁闷的出纳员

论 C++14(GCC9)。。。

为什么 C++14 会 CE 啊？

然后这个题，集体增减工资可以拿一个懒标记搞，插入的时候把懒标记减去的数值加到 Splay 里，然后每次查询一样查询，删除的时候把前驱 splay 到根节点，连同左子树删掉就完了。右子树的根节点成为新的根节点。

我个深必把右子树为空的情况忘记累加答案了。。。

居然还有 80pts。。。

时间复杂度 $O(n\log n)$。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include<iostream>
#include<cstdio>
#include<set>
#define ll long long
using namespace std;
namespace Ehnaev{
  inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<48||ch>57) {if(ch==45) f=-f;ch=getchar();}
    while(ch>=48&&ch<=57) {ret=(ret<<3)+(ret<<1)+ch-48;ch=getchar();}
    return ret*f;
  }
  inline void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
    else {putchar(45);do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
    while(len>=0) putchar(buf[len--]);
  }
}using Ehnaev::read;using Ehnaev::write;
inline void writeln(ll x) {write(x);putchar(10);}

const ll N=1e6;

ll laz,ans;
ll buffa[N+5],bufch[2][N+5],bufval[N+5],bufsiz[N+5],bufcnt[N+5];
ll *nowfa=buffa,*nowch[2]={bufch[0],bufch[1]},*nowval=bufval
  ,*nowsiz=bufsiz,*nowcnt=bufcnt;

struct Splay{
  ll *fa,*ch[2],*val,*siz,*cnt;ll rt,sz;
  inline void Init(ll x) {
    x+=5;fa=nowfa;ch[0]=nowch[0];ch[1]=nowch[1];val=nowval;
    siz=nowsiz;cnt=nowcnt;
    nowfa+=x;nowch[0]+=x;nowch[1]+=x;nowval+=x;nowsiz+=x;nowcnt+=x;
  }
  inline ll Get(ll x) {return x==ch[1][fa[x]];}
  inline void Pushup(ll x) {siz[x]=siz[ch[0][x]]+siz[ch[1][x]]+cnt[x];}
  inline void Rotate(ll x) {
    ll y=fa[x],z=fa[y],c=Get(x);ch[c][y]=ch[c^1][x];
    if(ch[c^1][x]) fa[ch[c^1][x]]=y;ch[c^1][x]=y;fa[y]=x;fa[x]=z;
    if(z) ch[y==ch[1][z]][z]=x;Pushup(y);Pushup(x);
  }
  inline void splay(ll x,ll g) {
    if(!x) return;
    for(ll f=fa[x];f=fa[x],f!=g;Rotate(x)) {
      if(fa[f]!=g) Rotate(Get(f)==Get(x)?f:x);
    }
    if(!g) rt=x;
  }
  inline ll Find(ll k) {
    if(!rt) return 0;ll cur=rt;
    while(ch[k>val[cur]][cur]&&k!=val[cur]) cur=ch[k>val[cur]][cur];
    splay(cur,0);return cur;
  }
  inline void Ins(ll k) {
    if(!rt) {val[rt=++sz]=k;cnt[sz]++;Pushup(sz);return;}
    ll cur=rt,f=0;
    while(1) {
      if(k==val[cur]) {cnt[cur]++;Pushup(cur);splay(cur,0);break;}
      f=cur;cur=ch[k>val[cur]][cur];
      if(!cur) {
        val[++sz]=k;cnt[sz]++;fa[sz]=f;ch[k>val[f]][f]=sz;
        Pushup(sz);Pushup(f);splay(sz,0);break;
      }
    }
  }
  inline ll Kth(ll k) {
    ll cur=rt;
    while(1) {
      if(ch[0][cur]&&k<=siz[ch[0][cur]]) cur=ch[0][cur];
      else {
        k-=siz[ch[0][cur]]+cnt[cur];
        if(k<=0) return splay(cur,0),cur;cur=ch[1][cur];
      }
    }
  }
  inline ll Pre(ll k) {
    Find(k);if(k>val[rt]) return rt;ll cur=ch[0][rt];
    while(ch[1][cur]) cur=ch[1][cur];splay(cur,0);return cur;
  }
  inline void Del(ll k) {
    Pre(k);if(val[rt]>=k) return;
    // printf("k=%lld val=%lld\n",k,val[rt]);
    if(ch[1][rt]) {
      // printf("ans=%lld\n",ans);
      ans+=siz[ch[0][rt]]+cnt[rt];rt=ch[1][rt];fa[rt]=0;return;
    }
    else {
      ans+=siz[ch[0][rt]]+cnt[rt];rt=0;return;
    }
  }
}t;

int main() {

  ll n,lim;n=read();lim=read();t.Init(n);
  for(ll i=1;i<=n;i++) {
    char op[5];ll x;scanf("%s",op);x=read();
    if(op[0]=='I') {if(x<lim) continue;t.Ins(x-laz);}
    if(op[0]=='A') {laz+=x;t.Del(lim-laz);}
    if(op[0]=='S') {laz-=x;t.Del(lim-laz);}
    if(op[0]=='F') {
      if(x>t.siz[t.rt]) writeln(-1);
      else writeln(t.val[t.Kth(t.siz[t.rt]-x+1)]+laz);
    }
  }

  writeln(ans);

  return 0;
}