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

2022-12-28
北京
本文字数：1881 字
阅读完需：约 6 分钟

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~ntype 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 curfunc (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}