题解：P11456 [USACO24DEC] Interstellar Intervals G

· · 题解

提供一种可以把本题变成绿题来做的单 \log 做法。

前置知识：树状数组区间加贡献。

首先，我们注意到对于一个位置 i，如果它要延伸出 x 个位置为 R，那么我们需要保证这 x 个位置上的字符不是 B，这 x 个位置后面的 x 个位置不是 R（感性理解一下吧，作者的语文真不好）。

然后我们发现如果填表 dp 好像不好处理限制条件（当然也好处理，只是因为本人最开始脑抽以为刷表每一个位置可以延伸的距离是一段区间然后就以为更好做），反正我们考虑刷表做。

注意到如果我们暴力刷表，我们会比较讨厌 R，例如 RXXRXXXX 这种情况，我们发现我们能涂 RX，但不能涂 RXXR这段区间，但是我们又能涂 RXXRXXXX这段区间，于是就会导致涂得长度不是一段区间，但是事实上，我们可能涂的区间数量是 O(\log n) 的，于是我们可以在 O(n\log n) 的时间复杂度下暴力解决这个问题。

下面给出每个位置可能涂的长度的区间数量是 O(\log n) 的证明：注意到如果我们有一个字符串 R...R...R 这样的（... 代表的是一段 X 或 R 组成的字符串），且满足前两个 R 之间的距离是大于后两个 R 之间的距离减一的，那么我们直接走到前两个 R 之间距离的两倍的区间中最后一个 R 的位置上判断有没有贡献即可，中间的显然没有贡献。否则我们就直接计算完走到第二个 R 的右边一个 R 即可，这样我们保证每两次这样的操作就会增加至少一倍距离，于是总的操作次数自然是 O(\log n) 的。

哦对了，X 可以当做 R 处理，但是如果一个位置是 X 的话，它的 dp 值应当是它到前一个不是 X 的字符上的 dp 值的和（包括它和前一个不是 X 的字符上的 dp 值）。

另外 R...B...R 这种情况也要考虑，注意到如果我们一旦遇到这种情况，可以立马退出处理 R...R...R 的情况的循环，因为之后一定没有贡献了，这种情况也比较好处理，读者不妨自己推导。

最后说一件事情，树状数组区间加是要分奇偶的。

然后就做完了，码量中等（但是相较于本题线性或者单 \log 略大），因此给个示例。

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

const int N = 5e5 + 10, mod = 1e9 + 7;
int n, pr[N], pb[N], sr[N], sb[N], sum[N];
char c[N];

struct BIT {
    int f[N / 2];
    void add(int x, int k) {
        for (; x <= n / 2 + 1; x += x & -x) {
            f[x] += k;
            if (f[x] >= mod) f[x] -= mod; 
        }
    }
    int qry(int x) { int res = 0; for (; x; x -= x & -x) res += f[x]; return res % mod; }
} tr[2];

signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> c[i];
    for (int i = 0; i <= n; ++i) {
        if (c[i] == 'B') pb[i + 1] = i, pr[i + 1] = pr[i];
        else if (c[i] == 'R') pb[i + 1] = pb[i], pr[i + 1] = i;
        else pb[i + 1] = pb[i], pr[i + 1] = pr[i];
    }
    sr[n + 1] = sb[n + 1] = n + 1;
    for (int i = n + 1; i >= 1; --i) {
        if (c[i] == 'B') sb[i - 1] = i, sr[i - 1] = sr[i];
        else if (c[i] == 'R') sb[i - 1] = sb[i], sr[i - 1] = i;
        else sb[i - 1] = sb[i], sr[i - 1] = sr[i];
    }
    tr[0].add(1, 1), tr[0].add(2, -1);
    for (int i = 0; i < n; ++i) {
        int id = i / 2 + 1, x = tr[i & 1].qry(id);
        sum[i] = (sum[i - 1] + x) % mod;
        if (c[i] == 'X') {
            if (max(pr[i], pb[i]) - 1 < 0) x = sum[i];
            else x = (sum[i] - sum[max(pr[i], pb[i]) - 1] + mod) % mod;
        }
        if (c[i + 1] == 'B') continue;
        int p = i + 1, flag = 0;
        while (p < n) {
            int l = p - i, r = sr[p] - p - 1;
            if (p + l > n) break;
            if (l > r) { p = pr[p + l + 1]; continue; }
            if (p > sb[i]) break;
            if (sr[p] > sb[i]) { flag = 1; break; }
            r = (sr[p] - i - 1) / 2;
            tr[i & 1].add(id + l, x), tr[i & 1].add(id + r + 1, -x);
            p = sr[p];
        }
        if (flag) {
            int l = max(1ll, pr[sb[i]] - i), r = min(sb[i] - i - 1, (sr[sb[i]] - i - 1) / 2);
            if (l > r) continue;
            tr[i & 1].add(id + l, x), tr[i & 1].add(id + r + 1, -x);
        }
    }
    int res = tr[n & 1].qry(n / 2 + 1);
    if (c[n] == 'X') res = res + sum[n - 1] - sum[max(pr[n], pb[n]) - 1];
    cout << (res % mod + mod) % mod;
    return 0;
}

后记：应该不会有人跟作者一样脑抽写树状数组变成双 \log 吧。事实上这题直接差分即可，可以做到单 \log。

贴一个单 \log 的示例吧。

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

const int N = 5e5 + 10, mod = 1e9 + 7;
int n, pr[N], pb[N], sr[N], sb[N], sum[N], s[2][N / 2];
char c[N];

signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> c[i];
    for (int i = 0; i <= n; ++i) {
        if (c[i] == 'B') pb[i + 1] = i, pr[i + 1] = pr[i];
        else if (c[i] == 'R') pb[i + 1] = pb[i], pr[i + 1] = i;
        else pb[i + 1] = pb[i], pr[i + 1] = pr[i];
    }
    sr[n + 1] = sb[n + 1] = n + 1;
    for (int i = n + 1; i >= 1; --i) {
        if (c[i] == 'B') sb[i - 1] = i, sr[i - 1] = sr[i];
        else if (c[i] == 'R') sb[i - 1] = sb[i], sr[i - 1] = i;
        else sb[i - 1] = sb[i], sr[i - 1] = sr[i];
    }
    ++s[0][1], --s[0][2];
    for (int i = 0; i < n; ++i) {
        int id = i / 2 + 1;
        s[i & 1][id] += s[i & 1][id - 1];
        int x = s[i & 1][id];
        sum[i] = (sum[i - 1] + x) % mod;
        if (c[i] == 'X') {
            if (max(pr[i], pb[i]) - 1 < 0) x = sum[i];
            else x = (sum[i] - sum[max(pr[i], pb[i]) - 1] + mod) % mod;
        }
        if (c[i + 1] == 'B') continue;
        int p = i + 1, flag = 0;
        while (p < n) {
            int l = p - i, r = sr[p] - p - 1;
            if (p + l > n) break;
            if (l > r) { p = pr[p + l + 1]; continue; }
            if (p > sb[i]) break;
            if (sr[p] > sb[i]) { flag = 1; break; }
            r = (sr[p] - i - 1) / 2;
            s[i & 1][id + l] += x, s[i & 1][id + r + 1] -= x;
            p = sr[p];
        }
        if (flag) {
            int l = max(1ll, pr[sb[i]] - i), r = min(sb[i] - i - 1, (sr[sb[i]] - i - 1) / 2);
            if (l > r) continue;
            s[i & 1][id + l] += x, s[i & 1][id + r + 1] -= x;
        }
    }
    s[n & 1][n / 2 + 1] += s[n & 1][n / 2];
    int res = s[n & 1][n / 2 + 1];
    if (c[n] == 'X') res = res + sum[n - 1] - sum[max(pr[n], pb[n]) - 1];
    cout << (res % mod + mod) % mod;
    return 0;
}

如果有想看填表的话可以看一下 Gold14526 的代码，他好像就是填表然后类似这样做。