题解 | 研究red子序列的红

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

const int MAXN = 2e5 + 5;

// 定义左子节点和右子节点的宏
#define ls(p) (p << 1)    // 左子节点
#define rs(p) (p << 1 | 1)  // 右子节点

// 定义线段树的结构体
struct SegTree {
    struct Seg {
        int l, r;  // 当前区间的左右端点
        int rcnt, ecnt, dcnt;  // 分别表示 r, e, d 的计数
        int recnt, edcnt;  // 表示 re 和 ed 的子序列数量
        int redcnt;  // 表示 red 子序列的数量
    } seg[MAXN << 2];  // 线段树节点数组，最多为 4n 个节点

    // push_up：合并左右子区间的信息，更新当前节点
    void push_up(int p) {
        // 合并 r, e, d 的计数
        seg[p].rcnt = seg[ls(p)].rcnt + seg[rs(p)].rcnt;
        seg[p].ecnt = seg[ls(p)].ecnt + seg[rs(p)].ecnt;
        seg[p].dcnt = seg[ls(p)].dcnt + seg[rs(p)].dcnt;

        // 合并 re 和 ed 的子序列数量
        seg[p].recnt =
            seg[ls(p)].recnt + seg[rs(p)].recnt + seg[ls(p)].rcnt * seg[rs(p)].ecnt;
        seg[p].edcnt =
            seg[ls(p)].edcnt + seg[rs(p)].edcnt + seg[ls(p)].ecnt * seg[rs(p)].dcnt;

        // 合并 red 子序列的数量
        seg[p].redcnt = seg[ls(p)].redcnt + seg[rs(p)].redcnt +
                        seg[ls(p)].recnt * seg[rs(p)].dcnt +
                        seg[ls(p)].rcnt * seg[rs(p)].edcnt;
    }

    // build：构建线段树，递归分治的过程
    void build(int l, int r, const string &s, int p) {
        seg[p].l = l, seg[p].r = r;
        if (l == r) {
            // 叶节点初始化，r, e, d 的计数
            seg[p].rcnt = seg[p].ecnt = seg[p].dcnt = 0;
            if (s[l] == 'r')
                seg[p].rcnt++;  // 如果是字符 'r'，增加 r 的计数
            else if (s[l] == 'e')
                seg[p].ecnt++;  // 如果是字符 'e'，增加 e 的计数
            else if (s[l] == 'd')
                seg[p].dcnt++;  // 如果是字符 'd'，增加 d 的计数
            return;
        }
        // 递归分治
        int mid = (l + r) >> 1;  // 计算中间点
        build(l, mid, s, ls(p));  // 构建左子树
        build(mid + 1, r, s, rs(p));  // 构建右子树
        push_up(p);  // 合并左右子树的结果
    }

    // update：单点修改，更新某位置的字符
    void update(int pos, char c, int p) {
        if (seg[p].l == seg[p].r && seg[p].l == pos) {
            // 如果是叶节点且是目标位置
            seg[p].rcnt = seg[p].ecnt = seg[p].dcnt = 0;  // 清空 r, e, d 的计数
            if (c == 'r')
                seg[p].rcnt = 1;  // 如果更新为 'r'，增加 r 的计数
            else if (c == 'e')
                seg[p].ecnt = 1;  // 如果更新为 'e'，增加 e 的计数
            else if (c == 'd')
                seg[p].dcnt = 1;  // 如果更新为 'd'，增加 d 的计数
            return;
        }
        int mid = (seg[p].l + seg[p].r) >> 1;  // 计算中间点
        if (pos <= mid)
            update(pos, c, ls(p));  // 如果目标位置在左子树，递归更新左子树
        else
            update(pos, c, rs(p));  // 如果目标位置在右子树，递归更新右子树
        push_up(p);  // 更新父节点的信息
    }

    // get_red_count：获取根节点的 red 子序列数量
    int get_red_count() {
        return seg[1].redcnt;  // 返回根节点的 red 子序列数量
    }
};

// 主函数：执行初始化、交换更新、查询并输出
signed main() {
    ios::sync_with_stdio(false);  // 提升 cin 性能
    cin.tie(nullptr);             // 禁用 cin 和 cout 的同步

    int n, q;
    cin >> n >> q;  // 读取字符串的长度和查询次数

    string s, t;
    cin >> s >> t;  // 读取两个字符串

    s = " " + s;  // 将字符串转为1-based索引
    t = " " + t;

    // 初始化线段树
    SegTree t1, t2;
    t1.build(1, n, s, 1);  // 为字符串 s 构建线段树
    t2.build(1, n, t, 1);  // 为字符串 t 构建线段树

    while (q--) {
        int x;
        cin >> x;  // 读取交换的位置
        // 执行交换并更新线段树
        swap(s[x], t[x]);  // 交换字符
        t1.update(x, s[x], 1);  // 更新 s 上的字符
        t2.update(x, t[x], 1);  // 更新 t 上的字符

        // 输出交换后的 red 子序列数量差值
        cout << t1.get_red_count() - t2.get_red_count() << "\n";
    }

    return 0;
}