题解 | 研究red子序列的红

输出结果和C++版一致，但是提交不通过，怀疑是系统问题。

class Node(object):  # 线段树的结点类
    def __init__(self):
        self.ln = -1
        self.rn = -1  # 左子节点和右子节点，值为字符的索引
        self.r = 0  # 分别记录 r, e, d, re, ed, red 的个数
        self.e = 0
        self.d = 0
        self.re = 0
        self.ed = 0
        self.red = 0


class SegTree(object):  # 线段树类
    def __init__(self, data):
        self.n = len(data)
        # 初始化线段树，大小为4*n（因为最坏情况下是满二叉树）
        self.tree = [Node() for _ in range(self.n * 4)]
        self.build(data, 1, 0, self.n - 1)  # 树节点从1开始

    def build(self, data, node, start, end):  # 构建线段树
        # data 表示字符串， node 表示节点下标，start 和 end 表示 字符的索引
        self.tree[node].ln = start
        self.tree[node].rn = end
        if start == end:  # 如果当前节点是叶子节点
            self.tree[node].r = int(data[start] == 'r')
            self.tree[node].e = int(data[start] == 'e')
            self.tree[node].d = int(data[start] == 'd')
            return
        mid = (start + end) // 2
        self.build(data, node * 2, start, mid)  # 左子树
        self.build(data, node * 2 + 1, mid + 1, end)  # 右子树
        self.push_up(node)

    def push_up(self, node):  # 计算该节点的r e d re ed red 个数
        left = self.tree[node * 2]  # 左节点
        right = self.tree[node * 2 + 1]  # 右节点
        self.tree[node].r = left.r + right.r
        self.tree[node].e = left.e + right.e
        self.tree[node].d = left.d + right.d
        self.tree[node].re = left.re + right.re + left.r * right.e
        self.tree[node].ed = left.ed + right.ed + left.e * right.d
        self.tree[node].red = left.red + right.red + left.re * right.d + left.r * right.ed

    def update(self, node, pos, val):  # 单点更新，pos表示更新的索引，val表示更新的值
        if self.tree[node].ln == self.tree[node].rn and self.tree[node].ln == pos:  # 递归到叶子节点
            self.tree[node].r = int(val == 'r')
            self.tree[node].e = int(val == 'e')
            self.tree[node].d = int(val == 'd')
            return
        mid = (self.tree[node].ln + self.tree[node].rn) // 2
        if pos <= mid:
            self.update(node * 2, pos, val)
        else:
            self.update(node * 2 + 1, pos, val)
        self.push_up(node)


n, q = map(int, input().split())
s = input()
t = input()
seg_s = SegTree(s)
seg_t = SegTree(t)
opt = []
for _ in range(q):
    x = int(input()) - 1
    opt.append(x)
for x in opt:
    seg_s.update(1, x, t[x])
    seg_t.update(1, x, s[x])
    s, t = s[:x] + t[x] + s[x + 1:], t[:x] + s[x] + t[x + 1:]
    print(seg_s.tree[1].red - seg_t.tree[1].red)