题解 CF1340F 【Nastya and CBS】

在博客园食用更佳：https://www.cnblogs.com/PinkRabbit/p/CF1340F.html。

题意简述

你需要动态维护一个多种括号组成的括号序列。需要支持两种操作：

1. 修改单一位置的括号。
2. 查询一段区间是否是一个合法的括号序列。

序列长度为 n，不同的括号种类数为 k，操作次数为 q。

一个多种括号组成的括号序列 S 是合法的当且仅当：

例如 ()[{}()] 和 {([{}])} 是合法的，而 ][][ 和 ([{)]} 不是。

题解

部分思路来自于 EntropyIncreaser。

我们考虑使用线段树维护，遇到的问题有二：

1. 线段树中的每个节点应该存储什么信息？
2. 如何合并信息？

考虑一段括号序列，在不断删去相邻的匹配括号之后，得到的结果。如果其中仍然包含了相向的括号（此时必然不匹配，因为如果匹配就会被删去），例如 (]，则在它两边再拼接上任何括号序列，最终都一定不会变成合法的括号序列。

如果已经可以确保区间内不可能变成合法的括号序列（也就是上述情况发生了），就可以打一个不可行的标记。

否则得到的结果一定是若干个右括号，加上若干个左括号（都可以为 0 个），例如 )]}[((。

可以发现只要在两边加上合适的括号，就可以把括号全部消除，变成合法的括号序列。

所以要记录的信息就是它，就是消到不能消之后的括号序列，分为「在左侧的右括号」和「在右侧的左括号」两部分。

先不考虑如何存储的问题，着眼于区间信息的合并上，如何合并两个子区间的信息呢？

我们令左子区间的左侧部分（右括号）为 ll，左子区间的右侧部分（左括号）为 lr，
　再令右子区间的左侧部分（右括号）为 rl，右子区间的右侧部分（左括号）为 rr，接下来分两种情况：

1. 如果 lr 比 rl 短。
   例如 )[( + )]}{( 这种情况，合并后变成 )}{(。
   可以发现必须有：整个 lr 要匹配得上 rl 的长度为 |lr| 的前缀。
   匹配上之后，再把 rl 的去掉这个前缀的部分连接在 ll 的后面，作为新的左侧部分，而右侧部分就是 rr。
   如果匹配不上，那就打上无解的标记。
2. 如果 lr 比 rl 长。
   例如 )[( + ){( 这种情况，合并后变成 )[{(。
   可以发现必须有：整个 rl 要匹配得上 lr 的长度为 |rl| 的后缀。
   匹配上之后，再把 lr 的去掉这个后缀的部分连接在 rr 的前面，作为新的右侧部分，而左侧部分就是 ll。
   如果匹配不上，那就打上无解的标记。

官方题解中使用了可持久化平衡树 + 哈希来维护信息，显然是可行的，而且时空复杂度都是 \mathcal O (n \log^2 n) 的。

实际上存在一种不那么麻烦，而且空间复杂度为线性的做法：

直接仅存储两部分的长度和字符串哈希值，不需要使用平衡树。

当合并的时候，需要查询某个节点左/右侧部分的某个长度的前/后缀的哈希值，和将要匹配的串进行比对。

但是已知整个串的哈希值是无法求出前/后缀的哈希值的，我们考虑递归！

实现两个函数来求某个节点左/右侧部分的前/后缀哈希值（详见代码中的 gValL 和 gValR 函数）。

以求左侧部分的前缀哈希值为例，如果要求长度为 0 或总长度就可以直接返回已知结果。
否则考虑要求的长度是否全部落在左子树的左侧部分内，如果是则直接递归左子树。
否则就是有一部分在左子树的左侧部分内，另一部分在右子树的左侧部分内，但是合并的时候会被左子树的右侧部分抵消掉一个前缀的数值，所以递归查询的时候，长度要减去左子树的左侧部分长度，但又要加上左子树的右侧部分长度，求出后再抵消掉左子树的右侧部分的一个前缀，再在前面拼上左子树的左侧部分。

右侧部分的后缀哈希值是对称的。虽然描述起来有些困难，但是如果封装了字符串哈希的一些操作，写起来会十分的简便。

可以发现若要查询此信息，每次只会递归到一个子树内，所以每次合并信息的复杂度是 \mathcal O (\log n) 的。

每次修改总共要合并 \mathcal O (\log n) 次信息，总复杂度为 \mathcal O (\log^2 n)。这与李超线段树或类楼房重建线段树的结构有些相似。

这部分就是修改时线段树内的维护了。还需要考虑询问时。

可以发现询问时，信息合并之后不再是一个原线段树上的节点了，而可以看作是「询问时建立的虚节点」。

因为信息合并时同样需要进行子树递归，在传统的递归结构中这是比较难以维护的。

我实现时先把在线段树上定位到的区间抽离出来，从左到右塞进一个栈中（详见代码中的 Extract 函数）。

然后利用询问时的特性（在任意时刻前缀不能含有左侧的右括号），维护一个 seq 数组进行更简易的模拟。

注意类似 gValR 的函数还需要针对 seq 实现一个，就是代码中的 gVal 函数。

具体细节详见代码。

评测记录，下面是代码，时间复杂度为 \mathcal O (n \log^2 n)，空间复杂度为 \mathcal O (n)：

#include <cstdio>

const int MN = 100005, MS = 1 << 18 | 7;

namespace Hashing {
    typedef long long LL;
    const int Mod = 998244353, B = 114514, iB = 137043501;
    int _w[MN * 2], *w = _w + MN;
    void Init(int N) {
        w[0] = 1;
        for (int i = 1; i <= N; ++i)
            w[i] = (LL)w[i - 1] * B % Mod,
            w[-i] = (LL)w[-i + 1] * iB % Mod;
    }
    struct str {
        int x, m;
        str() { x = m = 0; }
        str(int v) { x = v, m = 1; }
        str(int _x, int _m) : x(_x), m(_m) {}
        friend bool operator == (str a, str b) { return a.m == b.m && a.x == b.x; }
        friend str operator + (str a, str b) { return str((a.x + (LL)b.x * w[a.m]) % Mod, a.m + b.m); }
        friend str operator - (str a, str b) { return str((LL)(a.x - b.x + Mod) * w[-b.m] % Mod, a.m - b.m); }
    };
}
using Hashing::str;

int N, Q;

#define li (i << 1)
#define ri (li | 1)
#define mid ((l + r) >> 1)
#define ls li, l, mid
#define rs ri, mid + 1, r
struct dat {
    bool err;
    str vl, vr;
    dat() { err = 0; }
    dat(int x) { err = 0; x > 0 ? vr = str(x) : vl = str(-x); }
} tr[MS];
str gValL(int i, int k) {
    if (!k) return str();
    if (k == tr[i].vl.m) return tr[i].vl;
    if (k <= tr[li].vl.m) return gValL(li, k);
    return tr[li].vl + (gValL(ri, k - tr[li].vl.m + tr[li].vr.m) - tr[li].vr);
}
str gValR(int i, int k) {
    if (!k) return str();
    if (k == tr[i].vr.m) return tr[i].vr;
    if (k <= tr[ri].vr.m) return gValR(ri, k);
    return tr[ri].vr + (gValR(li, k - tr[ri].vr.m + tr[ri].vl.m) - tr[ri].vl);
}
void Upd(int i) {
    if (tr[li].err || tr[ri].err) return tr[i].err = 1, void();
    tr[i].err = 0;
    tr[i].vl = tr[li].vl;
    tr[i].vr = tr[ri].vr;
    if (tr[li].vr.m <= tr[ri].vl.m) {
        if (tr[li].vr == gValL(ri, tr[li].vr.m))
            tr[i].vl = tr[i].vl + (tr[ri].vl - tr[li].vr);
        else tr[i].err = 1;
    } else {
        if (tr[ri].vl == gValR(li, tr[ri].vl.m))
            tr[i].vr = tr[i].vr + (tr[li].vr - tr[ri].vl);
        else tr[i].err = 1;
    }
}
void Build(int i, int l, int r) {
    if (l == r) {
        int x;
        scanf("%d", &x);
        tr[i] = x;
        return ;
    }
    Build(ls), Build(rs);
    Upd(i);
}
void Mdf(int i, int l, int r, int p, int x) {
    if (l == r) return tr[i] = x, void();
    p <= mid ? Mdf(ls, p, x) : Mdf(rs, p, x);
    Upd(i);
}

int stk[45], tp;
void Extract(int i, int l, int r, int a, int b) {
    if (r < a || b < l) return ;
    if (a <= l && r <= b) return stk[++tp] = i, void();
    Extract(ls, a, b), Extract(rs, a, b);
}
str seq[45];
str gVal(int i, int k) {
    if (!k) return str();
    if (k == seq[i].m) return seq[i];
    if (k <= tr[stk[i]].vr.m) return gValR(stk[i], k);
    return tr[stk[i]].vr + (gVal(i - 1, k - tr[stk[i]].vr.m + tr[stk[i]].vl.m) - tr[stk[i]].vl);
}
bool Qur(int l, int r) {
    tp = 0, Extract(1, 1, N, l, r);
    for (int i = 1; i <= tp; ++i) {
        if (tr[stk[i]].err) return 0;
        if (seq[i - 1].m < tr[stk[i]].vl.m) return 0;
        if (tr[stk[i]].vl == gVal(i - 1, tr[stk[i]].vl.m))
            seq[i] = tr[stk[i]].vr + (seq[i - 1] - tr[stk[i]].vl);
        else return 0;
    }
    return !seq[tp].m;
}

int main() {
    scanf("%d%*d", &N);
    Hashing::Init(N);
    Build(1, 1, N);
    scanf("%d", &Q);
    while (Q--) {
        int t, x, y;
        scanf("%d%d%d", &t, &x, &y);
        if (t == 1) Mdf(1, 1, N, x, y);
        else puts(Qur(x, y) ? "Yes" : "No");
    }
    return 0;
}