题解 | 研究red子序列的红

package main

import (
	"fmt"
)
// 使用线段树算法，第一次直到这个算法，参考了其他人的设计
// go string 内容不可修改，多次询问可能会在s、t之间来回变换，需要转存到数组中
// 吐槽一下go的运行速度真的慢
type SegNode struct {
    rCnt int64
    eCnt int64
    dCnt int64
    reCnt int64
    edCnt int64
    redCnt int64
    l int
    r int
    left *SegNode
    right *SegNode
}
type SegTree struct {
    pool []SegNode
    p int
}
func (this *SegTree) NewNode() *SegNode{
    node := &this.pool[this.p]
    this.p++
    return node
}
func (this *SegTree) Init(n int) {
    this.pool = make([]SegNode, n)
    this.p = 0
}
func (this *SegNode) Build(l int, r int, data *string, tree *SegTree) {
    this.l = l
    this.r = r
    if l == r {
        c := (*data)[l]
        this.SetData(c)
        return
    }
    mid := (l + r) / 2
    left := tree.NewNode()
    this.left = left
    left.Build(l, mid, data, tree)
    right := tree.NewNode()
    this.right = right
    right.Build(mid + 1, r, data, tree)
    this.PushUp()
}

func (this *SegNode) PushUp() {
    left := this.left
    right := this.right
    this.rCnt = left.rCnt + right.rCnt
    this.eCnt = left.eCnt + right.eCnt
    this.dCnt = left.dCnt + right.dCnt
    this.reCnt = left.reCnt + right.reCnt + left.rCnt * right.eCnt
    this.edCnt = left.edCnt + right.edCnt + left.eCnt * right.dCnt
    this.redCnt = left.redCnt + right.redCnt + left.rCnt * right.edCnt + left.reCnt * right.dCnt
}

func (this *SegNode) Update(pos int, c byte) {
    if this.l == this.r && this.l == pos {
        this.rCnt = 0
        this.eCnt = 0
        this.dCnt = 0
        this.SetData(c)
        return
    }
    mid := (this.l + this.r ) /2
    if pos <= mid {
        this.left.Update(pos, c)
    } else {
        this.right.Update(pos, c)
    }
    this.PushUp()
}
func (this *SegNode) SetData(c byte) {
    switch c {
    case 'r':
        this.rCnt = 1
    case 'e':
        this.eCnt = 1
    case 'd':
        this.dCnt = 1
    }
}
func (this *SegNode) Show(pre string) {
    fmt.Printf("%+v\n",this)
    if this.left != nil {
        fmt.Printf("%sleft:", pre)
        this.left.Show(pre + "\t")
    }
    if this.right != nil {
        fmt.Printf("%sright:", pre)
        this.right.Show(pre + "\t")
    }
}
func main() {
    var n, q int
    fmt.Scan(&n, &q)
    var s, t string
    fmt.Scan(&s, &t)
    sv := make([]byte, n)
    tv := make([]byte, n)
    // go string 内容不可修改， 多次询问可能会导致同一个点位来回交换，因此需要修改字符串内容
    for i := 0; i < n; i++ {
        sv[i] = s[i]
        tv[i] = t[i]
    }
    tree := &SegTree{}
    tree.Init(n*4)
    sRoot := &SegNode{}
    sRoot.Build(0, n-1, &s, tree)
    tRoot := &SegNode{}
    tRoot.Build(0, n-1, &t, tree)
    //sRoot.Show("")
    for i := 0; i < q; i++ {
        var k int
        fmt.Scan(&k)
        k--
        tmp := sv[k]
        sv[k] = tv[k]
        tv[k] = tmp
        sRoot.Update(k, sv[k])
        tRoot.Update(k, tv[k])
        //fmt.Printf("switch %c<=>%c\n", s[k], t[k])
        //sRoot.Show("")
        fmt.Printf("%d\n", sRoot.redCnt - tRoot.redCnt)
    }
}