「解题报告」P9353 [JOI 2023 Final] Modern Machine

· · 题解

首先考虑一次操作干了什么，注意到我们只有在最后一次转弯后的覆盖是有意义的，那么实际上，将结果分为从左边出界和从右边出界，分别造成的修改是前缀染红与后缀染蓝。

那么考虑具体染了多少，大概手动模拟一下发现，如果在第 i 个位置操作，会将前 i 个蓝色染红或把后 n-i+1 个红染蓝。证明也很简单，以前一种情况为例，考虑左边与右边转弯的次数，左边遇到红色会转弯，后边遇到蓝色会转弯，设左边有 p 个蓝色，那么就有 i-1-p 个红色，于是会转 i-1-p 次弯，最后从左边出，说明在右边转了 i-p 次弯，于是右边覆盖了 i-p 个蓝色，于是总共覆盖的蓝色数就是 i 个。

那么暴力模拟这个过程就可以 O(nmq) 了，可以拿到 15 分。改成线段树上二分即可 O(mq \log n)，可以通过第三个包，拿到 25 分。

考虑第四、五个包怎么做，存在一个 t \in [0, n]，使得前 t 个为红色，剩下的都是蓝色。注意到，此时每次操作之后，原来的操作不会改变这个性质，仅改变了 t，那么我们实际上只需要考虑维护 t 即可。

由于开始会把所在的格子染红，所以起点在红与蓝上的情况会不同，简单分情况考虑一下：

可以发现，上述操作实际上是在模 n + 1 意义下进行加 i 或 i+1 的操作，我们可以写出一个函数 f_i(t)，表示在 i 操作下 t 会变成什么，那么有：

f_i(t) = \begin{cases} (t + i + 1) \bmod (n + 1) & t < i\\ (t + i) \bmod (n + 1) & t \ge i \end{cases}

那么，我们要求的，实际上就是一个区间内这个函数的复合。对于 n = 10 的情况，发现我们可以直接维护所有函数值，直接上线段树维护，复杂度 O(nq \log m)，可以通过第四个包，拿到 36 分。

直接维护函数值显然是很差的，我们能不能直接维护分段函数？看起来似乎复杂度爆炸，但是注意到我们只有查询操作没有修改操作，于是我们的线段树只要能建出来就行，而查询操作也不需要真的把函数复合找出来，因为我们只要求单点的值，所以查询的时候不需要将线段树上的若干个区间合并起来，于是我们不需要太关心合并两个区间的复杂度，不过我们还是需要关心分段函数的总段数的。

而注意到复合一次这个分段函数相当于进行 O(1) 次的裁剪拼接，这只会使分段函数增加 O(1) 段，于是 len 个函数的复合得到的是一个 O(len) 段的分段函数，那么我们就可以发现线段树上所有节点上的函数的段数之和是 O(m \log m) 的。由于合并的时候需要找到分割点的位置，需要二分，所以总建树的复杂度就是 O(m \log^2 m) 的，单次查询也是 O(\log^2 m) 的，所以总复杂度 O((m + q) \log^2 m)，可以通过第五个包，拿到 62 分。

一般情况呢？注意到，任意局面进行若干次操作后，一定会变成上述的局面，而由于每次操作都是前缀染红与后缀染蓝，我们只需要维护前缀红的数量 p 与后缀蓝的数量 q，如果某一时刻两者染的部分交叉了，那么说明此时已经变成了上述的情况。考虑每次操作，如果操作的点 i \le p，覆盖前缀则 p 会多覆盖 i 个蓝点，覆盖后缀则一定会变成前面所述的情况，q 是同理的，于是对于操作的点在 p,q 之内的情况，所进行的操作就是一直增加 p+q 的总和，我们只需要找到什么时候能够交叉即可。

如果操作的点不在 p,q 之内似乎就不好办了，不过我们注意到，进行一次操作后，无论增长的是 p 还是 q，它们都会翻倍，也就是说不在 p,q 内的点的操作只有 O(\log n) 次，于是我们只需要每次找到下一次不在 p, q 内的点，然后判断一下此时应该覆盖前缀还是后缀即可。

但是找 p,q 内的点是比较麻烦的，因为 p,q 一直在变。我们可以不严格找到所有 p,q 之内的点，而是只考虑小于等于 p,q 的最大的 2 的幂 x,y，这样我们只要对每个可能的 x,y 预处理出 i \le x 或者 i \ge n - y + 1 的 i 或 n-i+1 的前缀和与下一个 x < i < n - y + 1 的位置，这样不在 x,y 内的点仍然只有 O(\log n) 个，这样我们就可以每次跳一整段，看跳完之后是否 p,q 仍然不交，不交则找到新的 x,y 然后继续跳，交了则二分找到段内什么时候开始相交，于是这部分就可以在 O(m \log^2 n + q \log n) 的时间复杂度内解决了。

那么只需要把两部分拼在一起就做完这道题了。复杂度两个 \log。

有一些细节需要仔细考虑，大部分细节来自于操作时需要先把当前点修改为红色。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 120005, LOG = 18;
int n, m, T;
char s[MAXN];
int a[MAXN];
int px[MAXN], qx[MAXN], pc, qc, pi[MAXN], qi[MAXN];
int h(int x) { return x == 0 ? 0 : __lg(x) + 1; }
int nxt[LOG][LOG][MAXN];
long long ps[LOG][LOG][MAXN], qs[LOG][LOG][MAXN];
int preb[MAXN];
struct SegmentTree {
    vector<pair<int, int>> t[MAXN << 2];
#define lc (i << 1)
#define rc (i << 1 | 1)
    void build(int i = 1, int l = 1, int r = m) {
        if (l == r) {
            int v = a[l];
            if (v == n) t[i] = { { v - 1, v + 1 - n - 1 }, { n, v - n - 1 } };
            else if (n - v - 1 < v - 1) t[i] = { { n - v - 1, v + 1 }, { v - 1, v + 1 - n - 1 }, { n, v - n - 1 } };
            else t[i] = { { v - 1, v + 1 }, { n - v, v }, { n, v - n - 1 } };
            return;
        }
        int mid = (l + r) >> 1;
        build(lc, l, mid), build(rc, mid + 1, r);
        int L = 0;
        for (auto [R, v] : t[lc]) {
            auto it1 = lower_bound(t[rc].begin(), t[rc].end(), make_pair(L + v, INT_MIN));
            auto it2 = lower_bound(t[rc].begin(), t[rc].end(), make_pair(R + v, INT_MIN));
            for (auto it = it1; ; it++) {
                int rr = it == it2 ? R + v : it->first;
                t[i].push_back({ rr - v, v + it->second });
                if (it == it2) break;
            }
            L = R + 1;
        }
    }
    void query(int a, int b, int &v, int i = 1, int l = 1, int r = m) {
        if (a <= l && r <= b) {
            auto p = lower_bound(t[i].begin(), t[i].end(), make_pair(v, INT_MIN));
            v += p->second;
            return;
        }
        int mid = (l + r) >> 1;
        if (a <= mid) query(a, b, v, lc, l, mid);
        if (b > mid) query(a, b, v, rc, mid + 1, r);
    }
} st;
int main() {
    scanf("%d%d%s", &n, &m, s + 1);
    for (int i = 1; i <= m; i++) scanf("%d", &a[i]);
    for (int i = 1; i <= n + 1; i++) if (s[i] != 'R') px[++pc] = i - 1, pi[i - 1] = pc;
    for (int i = n; i >= 0; i--) if (s[i] != 'B') qx[++qc] = n - i, pi[n - i] = qc;
    for (int i = 1; i <= n; i++) preb[i] = preb[i - 1] + (s[i] == 'B');
    for (int x = 0; x < LOG; x++) {
        for (int y = 0; y < LOG; y++) {
            int X = x == 0 ? 0 : (1 << (x - 1));
            int Y = y == 0 ? 0 : (1 << (y - 1));
            nxt[x][y][m + 1] = m + 1;
            for (int i = m; i >= 1; i--) nxt[x][y][i] = (X < a[i] && a[i] < n + 1 - Y) ? i : nxt[x][y][i + 1];
            for (int i = 1; i <= m; i++) {
                ps[x][y][i] = (a[i] <= X ? a[i] : 0) + ps[x][y][i - 1];
                qs[x][y][i] = (a[i] > n - Y ? n - a[i] : 0) + qs[x][y][i - 1];
            }
        }
    }
    st.build();
    scanf("%d", &T);
    while (T--) {
        int l, r; scanf("%d%d", &l, &r);
        int p = 1, q = 1;
        int i = l - 1;
        int t = -1;
        auto Get = [&](int x) {
            if (x <= px[p]) return 'R';
            if (x > n - qx[q]) return 'B';
            return s[x];
        };
        while (1) {
            int x = h(px[p]), y = h(qx[q]);
            int j = min(nxt[x][y][i + 1], r + 1);
            int dp = min(ps[x][y][j - 1] - ps[x][y][i], 1ll * n);
            int dq = min(qs[x][y][j - 1] - qs[x][y][i], 1ll * n);
            if (px[min(pc, p + dp)] + qx[min(qc, q + dq)] < n) {
                p += dp, q += dq, i = j;
                if (j == r + 1) break;
                int bc = preb[n - qx[q]] - preb[px[p]] + qx[q], x = a[j] + (Get(a[j]) == 'B');
                if (x <= bc) {
                    if (x >= bc - qx[q]) { t = n - qx[q] + (x - (bc - qx[q])), l = j + 1; break; }
                    else p += x;
                } else {
                    int ac = n - bc, x = n - a[j] + (Get(a[j]) == 'R');
                    if (x >= ac - px[p]) { t = px[p] - (x - (ac - px[p])), l = j + 1; break; }
                    else q += x;
                }
            } else {
                int L = i + 1, R = j - 1;
                while (L < R) {
                    int mid = (L + R) >> 1;
                    int dp = min(ps[x][y][mid] - ps[x][y][i], 1ll * n);
                    int dq = min(qs[x][y][mid] - qs[x][y][i], 1ll * n);
                    if (px[min(pc, p + dp)] + qx[min(qc, q + dq)] < n) L = mid + 1;
                    else R = mid;
                }
                int dp = min(ps[x][y][L - 1] - ps[x][y][i], 1ll * n);
                int dq = min(qs[x][y][L - 1] - qs[x][y][i], 1ll * n);
                p += dp, q += dq, l = L + 1;
                int bc = preb[n - qx[q]] - preb[px[p]] + qx[q], x = a[L] + (Get(a[L]) == 'B');
                if (x <= bc) {
                    t = n - qx[q] + (x - (bc - qx[q]));
                } else {
                    int ac = n - bc, x = n - a[L] + (Get(a[L]) == 'R');
                    t = px[p] - (x - (ac - px[p]));
                }
                break;
            }
        }
        if (t == -1) {
            int ans = px[p] + n - qx[q] - px[p] - (preb[n - qx[q]] - preb[px[p]]);
            printf("%d\n", ans);
        } else {
            if (l <= r) st.query(l, r, t);
            printf("%d\n", t);
        }
    }
    return 0;
}