洛谷 P1486[NOI2004]郁闷的出纳员

发表于 | 分类于

题目

https://www.luogu.org/problemnew/show/P1486

题意

写一个工资统计程序，实现对每个员工工资的增加和扣除，对员工的雇佣和解雇，查询工资第k多的人

题解

这是第二次写这个题，第一次在这里不知道该怎么操作，想打标记也不好打，就看了题解，这次再写就会了。增加一个der变量，用来维护所有人工资的变化量，对于A操作，der+=k，对于S操作，der-=k，对于I操作，把员工工资插入splay的时候要减掉der。这样der就是所有员工工资的变化量了。然后就是普通的查询。写的时候我是把第k大的工资转换成了第k2小的工资来查询的，错了一组数据，我对比了下发现有一个查询出错了，不知道为啥，就改成了直接查询第k大的，就过了。

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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
#include <stdio.h>

const int MAXN = 2e5+10;
const int INF = 1e9;
struct node
{
    int ch[2];
    int val,cnt,sz,ff;
};
node t[MAXN];
int root,tot,sum,min,n;

void pushUp(int x)
{
    t[x].sz = t[t[x].ch[0]].sz + t[t[x].ch[1]].sz + t[x].cnt;
}

void Rotate(int x)
{
    int y = t[x].ff;
    int z = t[y].ff;
    int k = (t[y].ch[1] == x);
    t[z].ch[t[z].ch[1]==y] = x;
    t[x].ff = z;
    t[y].ch[k] = t[x].ch[k^1];
    t[t[x].ch[k^1]].ff = y;
    t[x].ch[k^1] = y;
    t[y].ff = x;
    pushUp(y);
    pushUp(x);
}

void Splay(int x, int goal)
{
    while(t[x].ff != goal)
    {
        int y = t[x].ff;
        int z = t[y].ff;
        if(z != goal)
            (t[z].ch[0]==y)^(t[y].ch[0]==x)?Rotate(x):Rotate(y);
        Rotate(x);
    }
    if(goal == 0) root = x;
}

void Find(int x)
{
    int u = root;
    if(!u) return;
    while(t[u].ch[x > t[u].val] && x != t[u].val)
        u = t[u].ch[x > t[u].val];
    Splay(u, 0);
}

void Insert(int x)
{
    int u = root, ff = 0;
    while(u && t[u].val != x)
    {
        ff = u;
        u = t[u].ch[x > t[u].val];
    }
    if(u)
        t[u].cnt++;
    else
    {
        u = ++tot;
        if(ff) t[ff].ch[x > t[ff].val] = u;
        t[u].ch[0] = t[u].ch[1] = 0;
        t[u].ff = ff;
        t[u].val = x;
        t[u].cnt = t[u].sz = 1;
    }
    Splay(u, 0);
}

int Next(int x, int f)
{
    Find(x);
    int u = root;
    if(t[u].val>x && f) return u;
    if(t[u].val<x && !f) return u;
    u = t[u].ch[f];
    while(t[u].ch[f^1]) u = t[u].ch[f^1];
    return u;
}

void Delete(int x)
{
    int next = Next(x, 1);
    Find(-INF);
    Splay(next, root);
    sum += t[t[next].ch[0]].sz;
    t[next].ch[0] = 0;
    pushUp(next);
    pushUp(root);
}

int KTh(int k)
{
    int u = root;
    while(true)
    {
        if(t[t[u].ch[1]].sz >= k)
            u = t[u].ch[1];
        else if(k > t[t[u].ch[1]].sz+t[u].cnt)
        {
            k -= (t[t[u].ch[1]].sz+t[u].cnt);
            u = t[u].ch[0];
        }
        else
            return t[u].val;
    }
}

int main()
{
    scanf("%d %d",&n,&min);
    Insert(-INF);
    Insert(INF);
    int der = 0,k;
    char ch;
    while(n--)
    {
        scanf(" %c %d",&ch,&k);
        if(ch == 'I')
        {
            if(k < min) continue;
            else Insert(k-der);
        }
        else if(ch == 'A')
        {
            der += k;
        }
        else if(ch == 'S')
        {
            der -= k;
            Delete(min-der-1);
        }
        else
        {
            if(k > t[root].sz-2) puts("-1");
            else printf("%d\n",KTh(k+1)+der);
        }
    }
    printf("%d\n",sum);
    return 0;
}