2022 China Collegiate Programming Contest (CCPC) Mianyang | 2022 CCPC 绵阳（MAEDJLB）

搬运自本人知乎文章。

https://zhuanlan.zhihu.com/p/588646549https://zhuanlan.zhihu.com/p/588646549

M. Rock-Paper-Scissors Pyramid

题目链接

题意

有一个长度为 $n$ 的石头剪刀布序列，每个元素是 RPS （石头、布、剪刀）中的一个，我们需要用这个序列构造一个三角，三角的底层为这个序列，第 $i(1\leq i < n)$ 层的第 $j$ 个元素为下一层第 $j$ 和 $j+1$ 个元素中不会失败的那一方。

求三角的顶端是什么。

Solution

考虑我们已经有了前 $n-1$ 位的序列生成的三角 $P$ ，我们从中推出 $n$ 位应该得到的三角 $P'$ 。

很显然，第 $n$ 位的元素应该会自底向上和 $P$ 的每一层的最后一个元素一一比较，如果能战胜，那么就在上一层的末尾放上自己，直到遇到第一个不能战胜的元素就结束，再向上的每层最后一个元素和下一层之前的最后一个元素相同。

显然这个过程中，只有每层最后一个元素有用，所以我们只维护每层最后一个元素，假设我们维护的这个序列为 $S$ 。同时，因为 $S$ 中连续相同位比较结果一定相同，我们可以把这些位看成一位。这样，由 $P$ 得到 $P'$ 的过程，等价于在 $S$ 末尾删除所有可以被新元素战胜的元素，然后将新元素加入 $S$ 末尾。

这个过程中 $S$ 可以用栈来表示，最后只需要输出栈底即可。

Code

#include<bits/stdc++.h>
using namespace std;

constexpr int N = 1e6 + 7;

bool beat(char s, char t) {
    if (s == 'R' && t == 'S') return 1;
    if (s == 'S' && t == 'P') return 1;
    if (s == 'P' && t == 'R') return 1;
    return 0;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    
    int T;
    cin >> T;
    while (T--) {
        string s;
        cin >> s;
        stack<int> sk;
        int n = s.size();
        for (int i = 0; i < n; ++i) {
            while (!sk.empty() && !beat(s[sk.top()], s[i])) sk.pop();
            sk.push(i);
        }
        int ans = 0;
        while (!sk.empty()) ans = sk.top(), sk.pop();
        cout << s[ans] << '\n';
    }

    return 0;
}

A. Ban or Pick, What’s the Trick

题目链接

Problem - A - Codeforces

题意

两个队伍分别可以选择 $n$ 个英雄，每个队伍可选的英雄的分值分别是 $\{a_n\}$ 和 $\{b_n\}$ 。双方轮流进行选择自己的英雄，或者禁用对方英雄池中的英雄。

最后双方各自最多选择自己挑选的英雄中的 $k$ 个出战，各自的总得分为各自选择的最多 $k$ 个影响的得分之和。双方都想最大化「己方得分 - 对方得分」，求出在双方各自最优策略下的最大分差。

Solution

显然，如果一个队伍挑选自己的英雄，他一定会选择自己池子中可选的分数最大英雄。同样，如果要禁用对方的英雄，那么他也一定会优先禁用对方池子中分数最大的英雄。

容易发现，如果一个队伍自己选满了 $k$ 个英雄，那么接下来如果再选英雄不会增加自己的得分，因此此后的操作一定会是禁用对方的英雄。

因此，双方各自选择的英雄不会超过 $k$ 个。

所以可以 DP。令 $dp[i][c1][c2]$ 表示第 $i$ 次操作前，第一队选择了 $c1$ 个英雄，第二队选择了 $c2$ 个英雄时，在接下来的过程中，能最大化的分差。

可以推出，在第 $i$ 次操作前，第一队进行了 $r1 = \lfloor \frac i2\rfloor$ 次操作，第二队进行了 $r2 = \lfloor \frac {i-1}2\rfloor$ 。因此双方各自被禁用了 $ban1 = r2 - c2$ 和 $ban2 = r1 - c1$ 个英雄，因此本次操作如果要选择英雄，应该选择第 $p1 = c1 + ban1 + 1$ 和 $p2 = c2 + ban2 + 1$ 大的英雄。

有了这些信息以后，直接枚举本次是自己选择英雄还是禁用对方的英雄转移即可。

注意对于第一队，如果 $c1 >= k$ 或者 $p1 > n$ 都意味着不能再选择自己的英雄了，而如果 $p2 > n$ 就不能禁用对方的英雄了。对于第二队同理。

可以使用记忆化搜索实现会更方便，时间复杂度 $O(nk^2)$ 。

Code

#include <bits/stdc++.h>
using namespace std;

#define fec(i, x, y) (int i = head[x], y = g[i].to; i; i = g[i].ne, y = g[i].to)
#define dbg(...) fprintf(stderr, __VA_ARGS__)
#define fi first
#define se second

using ll = long long; using ull = unsigned long long; using pii = pair<int, int>;

template <typename A, typename B> bool smax(A &a, const B &b) { return a < b ? a = b, 1 : 0; }
template <typename A, typename B> bool smin(A &a, const B &b) { return b < a ? a = b, 1 : 0; }

constexpr int N = 2e5 + 7;
constexpr int M = 13;
constexpr ll INF = LLONG_MAX / 2;

int n, k;
int a[N], b[N];
ll dp[N][M][M];
bool vis[N][M][M];

ll dfs(int x, int c1, int c2) {
    if (x == n * 2 + 1) return 0;
    if (vis[x][c1][c2]) return dp[x][c1][c2];
    vis[x][c1][c2] = 1;
    ll &ans = dp[x][c1][c2];
    int r1 = x / 2, r2 = (x - 1) / 2;
    int ban1 = r2 - c2, ban2 = r1 - c1;
    int p1 = c1 + ban1 + 1, p2 = c2 + ban2 + 1;
    if (x & 1) ans = max(p2 <= n ? -dfs(x + 1, c1, c2) : -INF, p1 <= n && c1 < k ? a[p1] - dfs(x + 1, c1 + 1, c2) : -INF);
    else ans = max(p1 <= n ? -dfs(x + 1, c1, c2) : -INF, p2 <= n && c2 < k ? b[p2] - dfs(x + 1, c1, c2 + 1) : -INF);
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= n; ++i) cin >> b[i];
    sort(a + 1, a + n + 1, greater<int>());
    sort(b + 1, b + n + 1, greater<int>());

    cout << dfs(1, 0, 0) << endl;
    
    return 0;
}

E. Hammer to Fall

题目链接

Problem - E - Codeforces

题意

有一个 $n$ 个点 $m$ 条边的无向图，每个点上有 $a_i$ 个人。

在 $q$ 天内，每天都会有一个点 $b_i$ 发生爆炸，而我们每天前都可以将若干人从一个城市转移到相邻的城市，代价是转移人数和边权的乘积。

我们需要最小化在不发生人员伤亡（保证爆炸时点上没有人）的情况下的最小代价和。

Solution

被转移的始终是人，而不同的人之间其实不会相互影响，所以我们可以计算单个人的代价。

只有每一天每个人在什么位置会对结果有影响，所以我们可以设 $dp_{i, x}$ 表示一个人第 $i$ 天在 $x$ 点时，在以后的时间中，保护这个人不受伤的最小代价。显然有

dp_{i, x} = \begin{cases} dp_{i+1, x}&, x \neq b_i\\ \min\limits_{(x, y, w) \in G} dp_{i+1, y} + w&, x = b_i \end{cases}\\

可以发现，如果在空间上省略第一维的天数，那么每天只会有一个点的答案发生改变，其余答案都可以直接继承。

我们考虑直接算出第 $i$ 天 $b_i$ 点的答案。这个答案需要从和这个点相邻的点中求得。但是暴力枚举所有的邻边最坏情况下是 $O(qn)$ 的。

对于这一类问题，有一种常用的方法是根号分治。令 $deg_x$ 为 $x$ 点的度数，假设 $blo$ 是我们分治的临界标准。

如果 $deg_x \leq blo$ ，那么我们暴力枚举和 $x$ 相邻的点即可直接计算出新的 $dp_{b_i}$ 。

如果 $deg_x > blo$ ，那么这样的点显然不会超过 $\frac{2m}{blo}$ 个（所有点度数之和为 $2m$ ）。对于每一个这样的 $x$ ，我们都可以用一个 multiset 维护其相邻点的 $dp_{y} + w$ 。在每一次更新了 $dp_{y}$ 时，就枚举所有的 $x$ ，如果 $x, y$ 相邻，从 $x$ 的 multiset 中把之前的 $dp_y + w$ 删除，加入新的值即可。在第 $i$ 天的时候，取出 $b_i$ 的 multiset 中最小的值就是新的 $dp_{b_i}$ 。

时间复杂度 $O(q(blo + \frac{2m}{blo}\log n))$ ，当 $blo = \sqrt{2m\log n}$ 时，最优复杂度为 $O(q\sqrt{2m\log n})$ 。

上面就是我们队在 vp 的时候现场的写法。但是这种写法并不是最优的。

如果在根号分治的同时带上时间分块的思想，可以避免 multiset 的使用。

时间分块的思想就是，我们如果每隔 $blo$ 天更新一次总体的信息，在此期间，我们特殊处理 $blo$ 天内的新信息，这样的新信息的规模不会超过 $O(blo)$ 个。

在此题中，我们在最近的 $blo$ 天内，最多会发生 $blo$ 个点的信息改变，而每个点的 $dp$ 值只有可能变大不会变小，因此 $blo$ 天内，每个 $deg_x > blo$ 的点的更新来源只可能是相邻的 $y$ 中在上一次整 $blo$ 倍天时 $dp_y + w$ 最小的 $blo + 1$ 个。

所以我们新的算法就是：

每到整 $blo$ 倍天，暴力求出每一个点 $x$ 的 $dp_y + w$ 最小的 $blo + 1$ 个邻居。可以使用 nth_element $O(deg_x)$ 地计算，这一步的总复杂度为 $\frac{q}{blo}m$ 。

如果 $deg_x\leq blo$ ，方法不变，仍然是暴力枚举和 $x$ 相邻的点计算 $dp_{b_i}$ 。

如果 $deg_x > blo$ ，那么暴力枚举之前维护好的 $x$ 个 $blo+1$ 个邻居，由它们更新 $dp_{b_i}$ 。

时间复杂度 $O(q\cdot blo + \frac{qm}{blo})$ ，当 $blo = \sqrt m$ 时有最小值 $O(q\sqrt m)$ 。

Code

#include <bits/stdc++.h>
using namespace std;

#define fec(i, x, y) (int i = head[x], y = g[i].to; i; i = g[i].ne, y = g[i].to)
#define dbg(...) fprintf(stderr, __VA_ARGS__)
#define fi first
#define se second

using ll = long long; using ull = unsigned long long; using pii = pair<int, int>;

template <typename A, typename B> bool smax(A &a, const B &b) { return a < b ? a = b, 1 : 0; }
template <typename A, typename B> bool smin(A &a, const B &b) { return b < a ? a = b, 1 : 0; }

constexpr int N = 1e5 + 7;
constexpr int M = 460 + 7;
constexpr ll INF = LLONG_MAX;
constexpr int P = 998244353;

int n, m, q, blo;
int deg[N], a[N], b[N];
ll dp[N];
bool mk[N];
vector<pii> g[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    
    cin >> n >> m >> q;
    blo = sqrt(m);
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1, x, y, z; i <= m; ++i) cin >> x >> y >> z, g[x].emplace_back(y, z), g[y].emplace_back(x, z), ++deg[x], ++deg[y];
    for (int i = q; i; --i) cin >> b[i];

    for (int i = 1; i <= n; ++i) if (deg[i] > blo)
        nth_element(g[i].begin(), g[i].begin() + blo, g[i].end(),
            [](const pii &x, const pii &y) { return dp[x.fi] + x.se < dp[y.fi] + y.se; });
    for (int i = 1; i <= q; ++i) {
        int x = b[i];
        dp[x] = INF;
        for (int i = 0; i < min(blo, deg[x]); ++i) smin(dp[x], dp[g[x][i].fi] + g[x][i].se);
        if (i % blo == 0) {
            for (int i = 1; i <= n; ++i) if (deg[i] > blo)
                nth_element(g[i].begin(), g[i].begin() + blo, g[i].end(),
                    [](const pii &x, const pii &y) { return dp[x.fi] + x.se < dp[y.fi] + y.se; });
        }
    }

    int ans = 0;
    for (int i = 1; i <= n; ++i) ans = (ans + a[i] * dp[i]) % P;
    cout << ans << endl;
    
    return 0;
}

D. Gambler’s Ruin

题目链接

Problem - D - Codeforces

题意

两个队伍打比赛，有 $n$ 个下注者，每个下注者对双方（BU 和 BC）胜率估计有一个预测 $p_i : 1-p_i$ 。

我们作为庄家要为两队开设赔率，BU 赢陪 $x$ ，BC 赢陪 $y$ ，如果一个下注者 $i$ 发现在他的胜率预测下，赌 BU 赢会期望赚钱（即 $p_ix \geq 1$ ），他就会给 BU 下注 $c_i$ 。否则，如果堵 BC 赢会期望赚钱，那么他就会给 $BC$ 下注 $c_i$ 。

我们需要最大化“最坏情况下”（两队中某队获胜）的收益，即若 $s_x, s_y$ 分别为 BU 和 BC 被下注总额，最大化 $s_x + s_y - \max\{s_xx, s_yy\}$ 。

Solution

即然只要 $p_ix\geq 1$ ， $i$ 就会给 $BU$ 下注，那么当 $x$ 确定，所有 $p_i \geq \frac 1x$ 的人就都会给 BU 下注。因此如果将所有下注者按照 $p_i$ 从大到小排序，那么下注 BU 的人一定是一个前缀。

同理，下注 BC 的人一定是一个后缀。

我们令 $pres_i$ 为排序后 $c_i$ 的前缀和， $sufs_i$ 为 $c_i$ 的后缀和。

那么我们枚举 $i$ 表示下注 BU 的前缀中最后一个人的指针， $j$ 为下注 BC 后缀中最前一个人的指针。那么最优情况下有 $x = \frac 1{p_i}, y = \frac 1{1 - p_j}$ 。

那么，收益 $pf$ 可以被写为

pres_i + sufs_j - \max\{ \frac{pres_i}{p_i}, \frac{sufs_j}{1 - p_j} \}\\

我们注意观察 $\max$ 中两个值，随着 $i$ 增大， $pres_i$ 在增大， $p_i$ 在减小，因此 $\frac{pres_i}{p_i}$ 一定会增大。

同时，随着 $j$ 增大， $sufs_j$ 在减小， $1 - p_j$ 在增大，因此 $\frac{sufs_j}{1 - p_j}$ 一定在减小。

因此，如果我们固定 $i$ ，一定会存在一个点 $p$ ，使得 $j \leq p$ 时 $\frac{pres_i}{p_i} \leq \frac{sufs_j}{1 - p_j}$ ，则在这一段内 $pf = pres_i - sufs_j \frac{p_j}{1 - p_j}$ 一定也在随 $j$ 增大而增大。

同时 $j > p$ 时 $\frac{pres_i}{p_i} > \frac{sufs_j}{1 - p_j}$ ，则这一段内 $pf = pres_i + sufs_j - \frac{pres_i}{p_i}$ 在随着 $j$ 的增大而减小。

也就是说，如果固定 $i$ ，那么最大的收益一定出现在 $j = p$ 或者 $j = p+1$ 上。

且，随着 $i$ 的增大， $p$ 的值应该会不断地减小，所以我们用双指针来维护 $p$ 的位置。

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

这个题有一个需要注意的点是，根据题意的要求，拥有相同的 $p_i$ 的人，一定会下注同一个队伍，因此我们可以把 $p_i$ 相同的人合并为一个人。

Code

#include <bits/stdc++.h>
using namespace std;

#define fec(i, x, y) (int i = head[x], y = g[i].to; i; i = g[i].ne, y = g[i].to)
#define dbg(...) fprintf(stderr, __VA_ARGS__)
#define fi first
#define se second

using ll = long long; using ull = unsigned long long; using pii = pair<int, int>;

template <typename A, typename B> bool smax(A &a, const B &b) { return a < b ? a = b, 1 : 0; }
template <typename A, typename B> bool smin(A &a, const B &b) { return b < a ? a = b, 1 : 0; }

constexpr int N = 1e6 + 7;
constexpr double eps = 1e-10;

int n;
pair<double, ll> a[N];
ll pres[N], sufs[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i].fi >> a[i].se;

    sort(a + 1, a + n + 1, greater<pair<double, int>>());
    int cnt = 0;
    for (int i = 1; i <= n; ++i)
        if (i == 1 || fabs(a[i].fi - a[i - 1].fi) > eps) a[++cnt] = a[i];
        else a[cnt].se += a[i].se;
    n = cnt;
    for (int i = 1; i <= n; ++i) pres[i] = pres[i - 1] + a[i].se;
    for (int i = n; i; --i) sufs[i] = sufs[i + 1] + a[i].se;
    
    double ans = 0;
    for (int i = 1, p = n; i <= n; ++i) if (i == n || fabs(a[i].fi - a[i + 1].fi) > eps) {
        while (p > i && pres[i] / a[i].fi > sufs[p] / (1 - a[p].fi)) --p;
        smax(ans, pres[i] + sufs[p + 1] - pres[i] / a[i].fi);
        if (i >= p) break;
        smax(ans, pres[i] + sufs[p] - sufs[p] / (1 - a[p].fi));
    }
    
    cout << fixed << setprecision(10) << ans << '\n';
    
    return 0;
}

J. Middle Race

题目链接

Problem - J - Codeforces

题意

给定三个正整数 $A, B, C$ 。

我、BoBo 和 oBoB 进行 $n$ 轮游戏，每轮游戏中我先选择 $A, B, C$ 中的一个数，然后 BoBo 和 oBoB 各自从剩下的数中选一个数。

设最后我、BoBo 和 oBoB 三个人 $n$ 轮选择的总和为 $X, Y, Z$ ，求出一种方案使得 $\min\{Y, Z\} \leq X \leq \max\{Y, Z\}$ 或者判断不存在。

Solution

感觉题面好绕，读了好几遍才读懂……

我到现在都不知道这个题为什么要出成交互，分明只要传统题的思路就能做了。

这个题让我卡了好久……试了好几种猜想，所幸最后还是想到了正确的思路。

因为需要让 $\min\{Y, Z\} \leq X \leq \max\{Y, Z\}$ ，可以想到，我们应该让 $X$ 尽可能地接近 $\frac S3$ ，其中 $S = n(A + B + C) = X + Y + Z$ 。

（因为这个题我试了两三种猜想都不对以后精神错乱，竟然写了一份直接让每一次的选择在向 $\frac {i(A + B + C)}3$ 靠近的 sb 逼近方法去交了一发……）

很容易证明，只要我们能求出这个 $X$ 最接近 $\frac S3$ 的方案，那么一定有 $\min\{Y, Z\} \leq X \leq \max\{Y, Z\}$ ：

假设 $Y \leq Z < X$ ，那么

|S - 3X| = |X + Y + Z - 3X| = |Y + Z - 2X| = 2X - Y - Z

|S - 3Z| = |X + Y + Z - 3Z| = |X + Y - 2Z|

。则， $|S - 3X| - |S - 3Z| =$

\begin{aligned} &\max\{ 2X - Y - Z - (X + Y - 2Z), 2X -Y - Z + (X + Y - 2Z) \}\\ = &\max\{ 2X - Y - Z - X - Y + 2Z), 2X -Y - Z + X + Y - 2Z \}\\ = &\max\{ X + Z - 2Y, 3X - 3Z\} > 0 \end{aligned}

即， $|S - 3X| > |S - 3Z|$ ，则 $X$ 不是最接近 $\frac S3$ 的，与假设矛盾。

$X < Y \leq Z$ 的假设和上面同理。

故只要 $X$ 最接近 $\frac S3$ ，就一定符合题意，故不存在无解。

下面考虑如何求出 $X$ 的构造方案。

不妨设 $A > B > C$ ，假设 $X$ 由 $a$ 个 $A$ ， $b$ 个 $B$ 和 $c$ 个 $C$ 构成，即 $a + b + c = n$

X = aA + bB + cC = aA + bB + (n - a - b)C = a(A - C) + b(B - C) + nC

。我们可以枚举 $a$ 的数量，然后通过二分 $b$ 可以找到令 $3X - S$ 的正负性改变的位置，进而求出最少 $|3X - S|$ 的最小值和构造方案。

单组数据时间复杂度 $O(n\log n)$ 。

Code

#include<bits/stdc++.h>
using namespace std;

#define fi first
#define se second

using ll = long long;
using ull = unsigned long long;

int n, m;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    
    int T;
    cin >> T;
    while (T--) {
        ll n, A, B, C;
        cin >> n >> A >> B >> C;
        if (A < B) swap(A, B);
        if (A < C) swap(A, C);
        if (B < C) swap(B, C);
        ll s = (A + B + C) * n;
        auto calc = [&](ll x1, ll x2) { return n * C + x1 * (A - C) + x2 * (B - C); };
        ll sta = LLONG_MAX, x1 = -1, x2 = -1;
        for (int i = 0; i <= n; ++i) {
            int l = 0, r = n - i;
            while (l < r) {
                int mid = (l + r) / 2;
                if (calc(i, mid) * 3 < s) l = mid + 1;
                else r = mid;
            }
            if (!(l == 0 || abs(calc(i, l) * 3 - s) <= abs(calc(i, l - 1) * 3 - s))) --l;
            ll p = abs(calc(i, l) * 3 - s);
            if (p < sta) x1 = i, x2 = l, sta = p;
        }
        for (int i = 1; i <= n; ++i) {
            if (i <= x1) cout << A << endl;
            else if (i <= x1 + x2) cout << B << endl;
            else cout << C << endl;
            int x, y;
            cin >> x >> y;
        }
    }

    return 0;
}

L. Por Una Cabeza

题目链接

Problem - L - Codeforces

题意

有 $n$ 个人，每个人会做出 $0/1$ 的投票。有 $m$ 台机器会处理投票结果，其接收奇数个输入，输入可以是人也可以是编号比它小的机器的输出，只要接受的输入中 $0$ 或 $1$ 的个数超过了应接收的输入的一半，机器就会直接给出输出。保证每个人的投票只会被一台机器直接处理，人按照编号顺序投票，可以认为机器的处理不需要时间。

每个人的投票 $a_i$ 已经给定了，我们可以花费 $b_i$ 使这个人改变他的投票，我们希望花费最少的钱来修改一些人的投票，使得每一个机器都只会在接收完所有输入以后才会输出结果。

有 $q$ 次操作，每次操作会修改一个投票人的 $a_i$ 和 $b_i$ 。输出修改后的最小花费。

Solution

假设一个机器的输入个数为 $l$ ，若要一个机器在接收完所有输入以后才会输出，那就要满足前 $l-1$ 个输入中， $0$ 和 $1$ 的数量都是 $\frac{l-1}2$ 。而在这样的条件下，机器的输出只会取决于最后输入的值。

因此，假设最后一个输入为 $p$ ，那么 $p$ 的值不影响在这个机器上的花费，但是可能会影响到这台机器输出的接收机器的花费，对于接收机器来说，输出机器可以直接看成 $p$ 在投票。

因此，如果我们只看一台机器需要的花费由哪些投票人组成，那么每一个投票人只会对一台机器产生贡献， $n$ 号投票人不对任何机器产生贡献。而机器之间的花费是相互独立的。

考虑如何计算一台机器的花费。假设这台机器关联的投票人有 $2k$ 个，其中有 $x$ 个 $0$ 和 $l - x$ 个 $1$ 。如果 $x > k$ ，那么我们需要将 $x - k$ 个投 $0$ 的人收买成 $1$ 。我们需要求出投 $0$ 的人中，花费最小的 $x - k$ 个的花费之和。对于 $x < k$ 来说也是同理。

因为 $x$ 每次变化量只可能为 $1$ ，所以可以使用两个对顶堆分别维护投 $0$ 和 $1$ 的人花费中前 $x - k$ 或 $k - x$ 小的部分。因为可能会修改单人花费，所以对顶堆中的每一个堆需要用可删除堆。

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

Code

这段代码由于我写的时候神智不清，写了一些很奇怪的东西。

传统的可删除堆应该是维护两个堆，其中一个堆专门存储被删除的数，但是我没有想起来可以这样搞，用了 unordered_map 来存储删除。

另外，对顶堆中其实只需要存储所有的花费，不必存储对应的投票人，所以不需要 pair，但是我一时没搞清楚所以多套了个 pair。

#include <bits/stdc++.h>
using namespace std;

#define fec(i, x, y) (int i = head[x], y = g[i].to; i; i = g[i].ne, y = g[i].to)
#define dbg(...) fprintf(stderr, __VA_ARGS__)
#define fi first
#define se second

using ll = long long; using ull = unsigned long long; using pii = pair<int, int>;

template <typename A, typename B> bool smax(A &a, const B &b) { return a < b ? a = b, 1 : 0; }
template <typename A, typename B> bool smin(A &a, const B &b) { return b < a ? a = b, 1 : 0; }

constexpr int N = 1e5 + 7;

int n, m, q;
int a[N], b[N];
int rv[N], fa[N], sz[N], c1[N];
vector<int> g[N];

struct HashFunc { size_t operator () (const pii &p) const { return hash<ull>()(((ll)p.fi << 32) + p.se); } };

template <class _Tp, class _Container = vector<_Tp>, class _Compare = less<typename _Container::value_type>>
struct Heap {
    priority_queue<_Tp, _Container, _Compare> q;
    unordered_set<_Tp, HashFunc> d;
    void re() { while (!q.empty() && d.count(q.top())) d.erase(q.top()), q.pop(); }
    void push(const _Tp &x) {
        if (d.count(x)) d.erase(x);
        else q.push(x);
        re();
    }
    bool empty() { return q.empty(); }
    _Tp top() { return q.top(); }
    void pop() { q.pop(); re(); }
    void del(const _Tp &x) { d.insert(x), re(); }
    size_t size() { return q.size() - d.size(); }
};

struct vHeap {
    int k;
    ll sum;
    Heap<pii> q;
    Heap<pii, vector<pii>, greater<pii>> nq;
    void ins(int x, int v) {
        q.push(pii(v, x)), sum += v;
        while (q.size() > k && !q.empty()) sum -= q.top().fi, nq.push(q.top()), q.pop();
    }
    void del(int x, int v) {
        if (!q.empty() && pair(v, x) <= q.top()) {
            q.del(pii(v, x)), sum -= v;
            while (q.size() < k && !nq.empty()) sum += nq.top().fi, q.push(nq.top()), nq.pop();
        } else nq.del(pii(v, x));
    }
    void modify(int x, int v, int nv) { del(x, v), ins(x, nv); }
    void modify(int nk) {
        assert(abs(nk - k) <= 1);
        k = nk;
        while (q.size() > k && !q.empty()) sum -= q.top().fi, nq.push(q.top()), q.pop();
        while (q.size() < k && !nq.empty()) sum += nq.top().fi, q.push(nq.top()), nq.pop();
    }
} h[N][2];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    
    cin >> n >> m >> q;
    for (int i = 1; i <= n; ++i) cin >> a[i] >> b[i];

    for (int i = 1; i <= m; ++i) {
        int l, mx = 0, &cnt1 = c1[i];
        cin >> l;
        vector<int> t;
        for (int j = 0, x; j < l; ++j) {
            cin >> x;
            if (x < 0) x = rv[-x];
            if (x > mx) mx && (t.push_back(mx), cnt1 += a[mx]), mx = x;
            else t.push_back(x), cnt1 += a[x];
        }
        rv[i] = mx, sz[i] = l - 1;
        assert(~t.size() & 1);
        if (cnt1 < t.size() / 2) h[i][0].k = t.size() / 2 - cnt1;
        else h[i][1].k = cnt1 - t.size() / 2;
        for (int x : t) h[i][a[x]].ins(x, b[x]), fa[x] = i;
    }

    ll ans = 0;
    for (int i = 1; i <= m; ++i) ans += h[i][0].sum + h[i][1].sum;
    
    for (int i = 1; i <= q; ++i) {
        int x, y, z;
        cin >> x >> y >> z;
        int f = fa[x];
        if (!f) goto end;
        ans -= h[f][0].sum + h[f][1].sum;
        if (y == a[x]) h[f][y].modify(x, b[x], z);
        else {
            h[f][a[x]].del(x, b[x]), h[f][y].ins(x, z);
            c1[f] += y - a[x];
            h[f][0].modify(max(sz[f] / 2 - c1[f], 0)), h[f][1].modify(max(c1[f] - sz[f] / 2, 0));
        }
        ans += h[f][0].sum + h[f][1].sum;
        end:
        a[x] = y, b[x] = z;
        cout << ans << '\n';
    }
    
    return 0;
}

B. Call Me Call Me

题目链接

Problem - B - Codeforces

题意

我们要邀请 $n$ 个人来参加会议。第 $i$ 个人会同意参加当且仅当区间 $[l_i , r_i]$ 内已经有 $k_i$ 个人同意参加。问最多能邀请多少个人来参加。

Solution

很显然的暴力做法就是类似于拓扑排序那样，先将所有的 $k_i = 0$ 的人入队，对于队列中的人 $x$ ，将所有的 $x\in[l_i, r_i]$ 的 $i$ 的 $k_i$ 减一，如果 $k_i$ 被减到了 $0$ ，就将 $i$ 入队。

考虑怎么优化这个过程，尤其是找到当前所有 $k_x = 0$ 的 $x$ 和找到 $x\in[l_i,r_i]$ 的 $i$ 的两个过程。

官方题解的做法非常神仙，我虽然大概能理解其思路，但是代码不是很好写。这里介绍的时间分治算法相比于官方题解，编写难度低了很多。

有一种很容易想出来的优化方法是结合线段树，将每一个人的区间 $[l_i, r_i]$ 挂到线段树上，分成 $O(\log n)$ 个区间，然后这样只需要 $O(\log n)$ 我们就可以找到所有的 $x\in[l_i, r_i]$ 的 $i$ 了。但是这样做只是加快了我们找到区间的时间，并没有可能找到的区间的个数，我们总共可能需要执行的 --k[i] 的次数在最坏情况下这依然是 $O(n^2)$ 的。

这是因为每一个区间都会被找到严格的 $k_i$ 次才能入队，我们需要一种方法，能够降低每个区间入队的次数。

可以考虑对时间分治，假设我们每 $blo$ 的时间整理一次数据。可以发现，我们在整 $blo$ 倍的时间后面长度为 $blo$ 的时间块中，最多有 $blo$ 个新处理（这里的处理指的是我们从队列中取出了一个人）的人，所以一个人有可能在接下来的 $blo$ 时间内入队，那么必须要满足当前的 $[l_i, r_i]$ 区间内已经处理过的人数 $+ blo \geq k_i$ 。我们把一个人在这个时候挂上线段树，他最多在线段树上被访问的次数不超过 $blo$ 次。

在整 $blo$ 倍的时间时，处理新挂上线段树的人的总复杂度 $O(\frac n{blo} n\log n)$ 。

被挂上线段树的人，最多在线段树上被访问的次数为 $O(n\cdot blo\log n)$ 。

当 $blo = \sqrt n$ 时复杂度最优，总复杂度为 $O(n\sqrt n\log n)$ 。

考虑到 $15s$ 的时间限制，勉强可以通过本题。

实际上线段树的 $\log n$ 和 $blo$ 次访问都很难跑满，所以总体上还是很快的。

官方题解里的分治+线段树的标算有空再慢慢写……

Code

#include <bits/stdc++.h>
using namespace std;

#define fec(i, x, y) (int i = head[x], y = g[i].to; i; i = g[i].ne, y = g[i].to)
#define dbg(...) fprintf(stderr, __VA_ARGS__)
#define fi first
#define se second

using ll = long long; using ull = unsigned long long; using pii = pair<int, int>;

template <typename A, typename B> bool smax(A &a, const B &b) { return a < b ? a = b, 1 : 0; }
template <typename A, typename B> bool smin(A &a, const B &b) { return b < a ? a = b, 1 : 0; }

constexpr int N = 4e5 + 7;
constexpr int M = 640;
constexpr int LOG = 19;

int n, blo;
struct Peo { int l, r, k; } a[N];
int s[N], vis[N], intr[N];
queue<int> q;

#define lc o << 1
#define rc o << 1 | 1
vector<int> t[N << 2];
void qins(int o, int L, int R, int l, int r, int k) {
    if (l <= L && R <= r) return t[o].push_back(k);
    int M = (L + R) / 2;
    if (l <= M) qins(lc, L, M, l, r, k);
    if (r > M) qins(rc, M + 1, R, l, r, k);
}
void del(int o) {
    vector<int> v;
    for (int i : t[o]) if (a[i].k) {
        --a[i].k;
        if (a[i].k) v.push_back(i);
        else q.push(i);
    }
    swap(t[o], v);
}
void qdel(int o, int L, int R, int x) {
    del(o);
    if (L == R) return;
    int M = (L + R) / 2;
    if (x <= M) qdel(lc, L, M, x);
    else qdel(rc, M + 1, R, x);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    
    cin >> n;
    blo = sqrt(n);
    for (int i = 1; i <= n; ++i) cin >> a[i].l >> a[i].r >> a[i].k;
    
    for (int i = 1; i <= n; ++i) if (!a[i].k) q.push(i), intr[i] = 1;
    int cnt = 0;
    while (!q.empty()) {
        int x = q.front(); q.pop();
        if (cnt % blo == 0) {
            for (int i = 1; i <= n; ++i) s[i] = s[i - 1] + vis[i];
            for (int i = 1; i <= n; ++i) if (!intr[i] && s[a[i].r] - s[a[i].l - 1] + blo >= a[i].k) {
                a[i].k -= s[a[i].r] - s[a[i].l - 1];
                qins(1, 1, n, a[i].l, a[i].r, i);
                intr[i] = 1;
            }
        }
        ++cnt;
        qdel(1, 1, n, x), vis[x] = 1;
    }
    cout << cnt << endl;
    
    return 0;
}

本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。