2022-12-28：有n个黑白棋子，它们的一面是黑色，一面是白色

2022-12-28：有n个黑白棋子，它们的一面是黑色，一面是白色，
它们被排成一行，位置0~n-1上。一开始所有的棋子都是黑色向上，
一共有q次操作，每次操作将位置标号在区间[L，R]内的所有棋子翻转，
那么这个范围上的每一颗棋子的颜色也就都改变了，
请在每次操作后，求这n个棋子中，黑色向上的棋子个数。
1 <= n <= 10^18，
1 <= q <= 300，
0 <= 每一条操作的L、R <= n - 1，
输出q行，每一行一个整数，表示操作后的所有黑色棋子的个数。
注意 : 其实q <= 10^5也可以通过，360考试时候降低了难度。
来自360。

答案2022-12-28：

动态开点线段树。
这道题用rust和shell都不好写，所以用golang。

代码用golang编写。代码如下：

package main

import (
    "fmt"
    "math/rand"
    "time"
)

func main() {
    rand.Seed(time.Now().Unix())
    N := 1000
    testTimes := 5000
    opTimes := 500
    fmt.Println("功能测试开始")
    for i := 0; i < testTimes; i++ {
        n := rand.Intn(N) + 1
        right := NewRight(n)
        dst := NewDynamicSegmentTree(n)
        pass := true
        for j := 0; j < opTimes; j++ {
            a := rand.Intn(n)
            b := rand.Intn(n)
            l := getMin(a, b)
            r := getMax(a, b)
            right.reverse(l, r)
            dst.reverse(l, r)
            if right.blacks() != dst.blacks() {
                pass = false
                return
            }
        }
        if !pass {
            fmt.Println("出错了!")
            break
        }
    }
    fmt.Println("功能测试结束")
}

func getMax(a, b int) int {
    if a > b {
        return a
    } else {
        return b
    }
}

func getMin(a, b int) int {
    if a < b {
        return a
    } else {
        return b
    }
}

// 为了测试
// 暴力方法
type Right struct {
    white []bool
}

func NewRight(n int) *Right {
    return &Right{white: make([]bool, n)}
}

func (this *Right) reverse(l, r int) {
    if l <= r {
        for i := l; i <= r; i++ {
            this.white[i] = !this.white[i]
        }
    }
}

func (this *Right) blacks() int {
    ans := 0
    for _, s := range this.white {
        if !s {
            ans += 1
        }
    }
    return ans
}

// 正式结构的实现
// 动态开点线段树
// 1 ~ 10^18 -> node
// l ~ r -> node
// l ~ r -> sum(黑子的数量)
// l ~ r -> 当前有没有翻转的动作需要往下传
type Node struct {
    sum    int
    change bool
    left   *Node
    right  *Node
}

func NewNode(len int) *Node {
    ans := &Node{}
    ans.sum = len
    ans.change = false
    return ans
}

// n = 10^18
// DynamicSegmentTree dst = new DynamicSegmentTree(n);
// int[] c1 = {4, 4000万}  dst.reverse(c1[0], c1[1]) -> dst.blacks
// int[] c2 ...
// ...

// c1 [l, r] 翻转， 数量 1~n
// c2 [l, r] 翻转， 数量 1~n
type DynamicSegmentTree struct {
    // 1 ~ n
    root *Node
    size int
}

func NewDynamicSegmentTree(n int) *DynamicSegmentTree {
    ans := &DynamicSegmentTree{}
    ans.root = NewNode(n)
    ans.size = n
    return ans
}

func (this *DynamicSegmentTree) blacks() int {
    return this.root.sum
}

// l++ r++
// 0, 7  -> 1,8
// 4, 19 -> 5, 20
// 19, 4 -> 不操作
func (this *DynamicSegmentTree) reverse(l, r int) {
    if l <= r {
        l++
        r++
        this.reverse0(this.root, 1, this.size, l, r)
    }
}

// l...r 线段树范围  s...e 任务范围
// Node cur
func (this *DynamicSegmentTree) reverse0(cur *Node, l, r, s, e int) {
    if s <= l && r <= e {
        cur.change = !cur.change
        cur.sum = (r - l + 1) - cur.sum
    } else {
        m := (l + r) >> 1
        this.pushDown(cur, m-l+1, r-m)
        if s <= m {
            this.reverse0(cur.left, l, m, s, e)
        }
        if e > m {
            this.reverse0(cur.right, m+1, r, s, e)
        }
        this.pushUp(cur)
    }
}

func (this *DynamicSegmentTree) pushDown(cur *Node, ln, rn int) {
    if cur.left == nil {
        cur.left = NewNode(ln)
    }
    if cur.right == nil {
        cur.right = NewNode(rn)
    }
    if cur.change {
        cur.left.change = !cur.left.change
        cur.left.sum = ln - cur.left.sum
        cur.right.change = !cur.right.change
        cur.right.sum = rn - cur.right.sum
        cur.change = false
    }
}

func (this *DynamicSegmentTree) pushUp(cur *Node) {
    cur.sum = cur.left.sum + cur.right.sum
}

本作品采用《CC 协议》，转载必须注明作者和本文链接