2022-12-28：有n个黑白棋子，它们的一面是黑色，一面是白色， 它们被排成一行，位置0~n-1上。一开始所有的棋子都是黑色向上， 一共有q次操作，每次操作将位置标号在区间[L，R]内的所有棋子翻

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

}

2022-12-28：有n个黑白棋子，它们的一面是黑色，一面是白色， 它们被排成一行，位置0~n-1上。一开始所有的棋子都是黑色向上， 一共有q次操作，每次操作将位置标号在区间[L，R]内的所有棋子翻的相关教程结束。