自动搬运

查看原文

来自洛谷，原作者为

	APJifengc 不拿 Au 不改签名

搬运于2025-08-24 22:47:36，当前版本为作者最后更新于2023-12-10 20:57:26，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

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

那么考虑具体染了多少，大概手动模拟一下发现，如果在第 $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$ 即可。

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

• 若起点 $i$ 为红色：
  • 若 $n - t \ge i$，则 $t \gets t + i$；
  • 否则，$t \gets t - (n - i + 1)$；
• 若起点 $i$ 为蓝色：
  • 若 $n - t - 1 \ge i$，则 $t \gets t + i + 1$；
  • 否则，$t \gets t - (n - i)$；

可以发现，上述操作实际上是在模 $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;
}