"> Sakits的游戏（线段树） | Stillwtm's Blog

Stillwtm's Blog
0%

Sakits的游戏（线段树）

发表于 更新于 分类于 阅读数： 评论数：
本文介绍一道线段树的运用题，具有一定的思维含量

原题

题目描述

Sakits最近沉迷一款打boss游戏，游戏里有$n$个boss，其中第$i$个boss战力为$w_i$，若Sakits的战力$W$，那他能打赢第$i$个boss当且仅当$W$>$w_i$，并且打赢后Sakits的战力会提升$w_i$。游戏的版本也会随着时间更新，会存在boss的增加和删除。

共有$Q$个操作，每个操作是下面三种类型之一。

$1\ W\ k$ ：Sakits的初始战力为$W$，Sakits至少打赢多少个boss才能将战力提升到$k$ （打boss的顺序随意，注意每个boss只能被击败一次）。

$2\ W$：新增一个战力为$W$的boss。

$3\ W$ ：删除一个战力为$W$的boss，保证一定存在。

输入格式

第一行一个正整数$n$。

第二行$n$个正整数$w_1,w_2,\cdots,w_n$。

第三行一个正整数$Q$。接下来$Q$行，每行若干个整数，描述一个操作，格式如题面所述。

输出格式

对于每一个$1$操作，输出一个整数表示答案（若无法将战力提升到$k$,输出”-1”）。

数据范围

$n\le 300000,q\le 100000,1\le w_i,w\le 10^{12},1\le W,k<=10^{18}$

思路分析

我们先简化一下问题，在不考虑添加和删除操作，只有询问的情况下，应该怎么做呢？朴素的想法是找到打不过的boss里$w$最小的一个，不妨记为$nxt$，然后在能打过的boss从大往小打，直到能打过$nxt$并把它打掉，然后再不断重复这个过程，直到战斗力达到$k$了为止。这是一个比较显然的贪心想法，它能保证我们打掉的boss数是最少的。

思路比较简单，但有几个实现上的问题。一是怎么查找$nxt$。朴素地找每次需要$O(n)$遍历一遍，这不太合适，考虑到我们本身就是依赖于大小进行查找，于是可以进行排序+二分，将每次查找的时间复杂度降到$O(logn)$。二是由于每个boss只能打一次，怎么去维护这件事情并且在下一次询问的时候复原。事实上，由于打掉的boss一定是连续排列的，所以在没有添加和删除的情况下，我们只需要拿一个指针指一下目前已经打到哪儿了即可。

然而，出题人不是很友好，如果考虑添加和删除操作，直接采用上面的做法就不太合适，毕竟添加元素意味着需要重新排序，而每次都重排显然超时了。于是，我们需要利用一点小技巧，让上面的思路可以继续生效，即采用离线做法。

所谓离线，就是先把所有操作和询问读进来，最后统一处理

我们把可能出现的元素都放进一个数组里（即原来就有的和将来可能添加的），然后进行排序和去重，并且增加一个数组$cnt_i$来记录$w_i$出现的次数。这样，当我们添加$W$的时候，就可以将$W$对应的$cnt+1$，而还没添加的就可以用$cnt=0$来表示，二分的时候检查是否添加即可。

由于添加和删除会改变$cnt$和前缀和，我们还要考虑高效地维护它们。很自然地，我们想到可以使用线段树。把连续的一段boss全打死，相当于把这一段的和全部置零，同时$cnt$也要置零，于是我们用线段树去维护一个$sum$用来记录区间里的所有$w_i\times cnt_i$之和，再维护一个$num$来记录区间里的$cnt$之和。

还有个问题，是原本的二分查找也需要修改。由于单点询问$cnt$是$O(logn)$的复杂度，再套一个二分就是$O(log^2n)$，这其实不太优。我们可以直接在树上进行二分操作，甚至还可以将区间修改一并顺带进行。简述一下，就是先往大的区间里找，如果这个区间能全部打掉，就把这个区间整个修改，否则就继续进入小区间。

最后，我们每次询问结束之后，我们需要对这颗线段树进行还原，笔者的想法比较暴力，就是每次修改之前把这个节点压到栈里，询问结束之后按序弹出栈复原即可。

贴上代码：

代码仅供参考，请不要盲目抄袭代码来完成作业！！！

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
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
#include <iostream>

typedef long long LL;

const int MAXN = 400000 + 10;
const int MAXQ = 100000 + 10;

typedef long long LL;

int numW;
LL w[MAXN];
int cnt[MAXN];
bool inBegin[MAXN];

struct Query {
    int opt;
    LL w, k;
} q[MAXQ];

class SegmentTree {
#define lson (x << 1)
#define rson (x << 1 | 1)
#define num(x) tree[x].num
#define sum(x) tree[x].sum
friend int solve(LL curW, LL k);
private:
    struct Node {
        int num;
        LL sum;
        Node operator+(const Node& rhs) const {
            return {rhs.num + num, rhs.sum + sum};
        }
    } tree[MAXN << 2];

    struct Record {
        Node val;
        int id;
    } rec[MAXN << 2];
    int top;

public:
    SegmentTree() : top(0) { }

    void pushUp(int x) {
        tree[x] = tree[lson] + tree[rson];
    }

    void build(int x, int l, int r) {
        if (l == r) {
            num(x) = cnt[l];
            sum(x) = cnt[l] * w[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(lson, l, mid);
        build(rson, mid + 1, r);
        pushUp(x);
    }

    void add(int x, int l, int r, LL val) {
        if (l == r) {
            sum(x) += val, num(x)++;
            return;
        }
        int mid = (l + r) >> 1;
        if (val <= w[mid]) add(lson, l, mid, val);
        else add(rson, mid + 1, r, val);
        pushUp(x);
    }

    void del(int x, int l, int r, LL val) {
        if (l == r) {
            sum(x) -= val, num(x)--;
            return;
        }
        int mid = (l + r) >> 1;
        if (val <= w[mid]) del(lson, l, mid, val);
        else del(rson, mid + 1, r, val);
        pushUp(x);
    }

    int findNext(int x, int l, int r, LL val) {  // 查找下一个能打过的
        if (!num(x) || val > w[r]) return 0;
        if (l == r) return l;
        int mid = (l + r) >> 1;
        int ret = findNext(lson, l, mid, val);
        if (ret) return ret;
        return findNext(rson, mid + 1, r, val);
    }

    void record(int x) {  // 压栈记录节点
        rec[++top] = {tree[x], x};
    }

    void rollBack() {  // 复原
        for (int i = top; i >= 1; i--) {
            tree[rec[i].id] = rec[i].val;
        }
        top = 0;
    }

    Node work(int x, int l, int r, LL curW, LL target) {
        if (w[l] >= curW || !num(x)) return {0, 0};  // 这段区间里的boss一个也打不过或者已经全打完了
        if (sum(x) <= target && w[r] < curW) {  // 这一段全部打掉
            record(x);  // 记录
            tree[x] = {0, 0};  // sum和num都赋成0
            return rec[top].val;
        }
        if (l == r) {  // 只有在叶子节点可能出现cnt不需要清零的情况
            record(x);
            int cnt = (target + w[l] - 1) / w[l];  // 上取整，只要打cnt个就到目标了
            sum(x) -= cnt * w[l], num(x) -= cnt;
            return {cnt, cnt * w[l]};
        }
        int mid = (l + r) >> 1;
        Node ret = work(rson, mid + 1, r, curW, target);  // 先找右边大的部分
        if (ret.sum < target) ret = ret + work(lson, l, mid, curW, target - ret.sum);  // 不够就继续往左边找
        record(x);
        pushUp(x);
        return ret;
    }
} tree;

inline LL read() {
    char c = getchar(); LL ret = 0, sig = 1;
    while (!isdigit(c)) { if (c == '-') sig = -1; c = getchar(); }
    while (isdigit(c)) { ret = ret * 10 + c - '0'; c = getchar(); }
    return ret * sig;
}

void sort(int l, int r, LL a[]) {  // 升序排序
    LL mid = a[(l + r) >> 1];
    int i = l, j = r;
    while (i <= j) {
        while (a[i] < mid) i++;
        while (a[j] > mid) j--;
        if (i <= j) {
            std::swap(a[i], a[j]);
            std::swap(inBegin[i], inBegin[j]);
            i++, j--;
        }
    }
    if (l < j) sort(l, j, a);
    if (i < r) sort(i, r, a);
}

int unique(int l, int r, LL a[]) {  // 去重，并返回去重后的数组长度
    int p = l;
    cnt[l] = inBegin[l];
    for (int i = l + 1; i <= r; i++) {
        if (a[i] != a[p]) {
            a[++p] = a[i];
            cnt[p] = inBegin[i];
        } else {
            cnt[p] += inBegin[i];
        }
    }
    return p - l + 1;
}

int solve(LL curW, LL k) {
    int ret = 0;
    while (curW < k) {
        int nxt = tree.findNext(1, 1, numW, curW);  // 找下一个想要打过的
        LL target = (nxt ? std::min(w[nxt] + 1, k) : k);
        SegmentTree::Node plus = tree.work(1, 1, numW, curW, target - curW);  // 二分+区间修改的过程
        if (plus.sum + curW < target) break;  // 达不到target，失败退出
        curW += plus.sum;
        ret += plus.num;
    }
    tree.rollBack();  // 对线段树进行复原
    return curW < k ? -1 : ret;
}

int main() {
    int n = read();
    for (int i = 1; i <= n; i++) {
        w[i] = read();
        inBegin[i] = true;
    }
    numW = n;
    int Q = read();
    for (int i = 1; i <= Q; i++) {  // 离线过程，将所有可能出现的boss全部放进w里
        q[i].opt = read();
        q[i].w = read();
        if (q[i].opt == 1) {
            q[i].k = read();
        } else if (q[i].opt == 2) {
            w[++numW] = q[i].w;
        }
    }
    sort(1, numW, w);
    numW = unique(1, numW, w);
    tree.build(1, 1, numW);
    for (int i = 1; i <= Q; i++) {
        if (q[i].opt == 1) {
            printf("%d\n", solve(q[i].w, q[i].k));
        } else if (q[i].opt == 2) {
            tree.add(1, 1, numW, q[i].w);
        } else if (q[i].opt == 3) {
            tree.del(1, 1, numW, q[i].w);
        }
    }
    return 0;
}

一些补充

细心的读者可能会注意到，上面的线段树在区间修改时没有打lazytag并进行标记下传，为什么呢？

这是由于这道题的特殊性，因为战斗力只会增加，所以当前能够整体访问的区间在战斗力增加后一定仍然能够整体访问，所以不用进行标记下传。

另外在时间复杂度方面，这道题似乎不是那么直观。在solve()函数中，由于每次会吃掉一个当前本来打不败的boss，所以战斗力至少每次会翻倍，而$k \leq 10^{18}$，故在粗略分析下，外层的while (curW < k)循环至多进行$logk_{max} = log10^{18} \approx 60$次。findNext()函数时间复杂度是$O(logn)$的，work()函数的分析比较复杂，实际上可以看成求出需要打的区间$[s,t]$，并对区间$[s, t]$进行区间修改，这两个过程分开每个都是$O(logn)$的，合并自然也是$O(logn)$的。至于rollBack()操作，从上面可以看出，每次询问访问的节点总数应该在$60\times logn$级别，不会过大。

于是本题总时间复杂度在$O(qlognlogk_{max})$级别。

上述内容只是粗浅的分析，如果出现错误或疏漏，欢迎在评论区指正