1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
|
type SegmentTree struct {
originalArr []int
// lazyTree[i] 表示节点 i 的后代节点节点是否要执行 0-1 翻转
lazyTree []bool
tree []int
}
func NewSegmentTree(arr []int) *SegmentTree {
n := len(arr)
originalArr := make([]int, n)
copy(originalArr, arr)
sTree := &SegmentTree{
tree: make([]int, 4*n),
lazyTree: make([]bool, 4*n),
originalArr: originalArr,
}
sTree.build(0, n-1, 1)
return sTree
}
func (st *SegmentTree) ReverseRange(l, r int) {
st.modify(l, r, 0, len(st.originalArr)-1, 1)
}
func (st *SegmentTree) SumRange(l, r int) int {
return st.query(l, r, 0, len(st.originalArr)-1, 1)
}
func (st *SegmentTree) build(a, b, idx int) {
if a == b {
st.tree[idx] = st.originalArr[a]
} else {
mid := a + (b-a)/2
st.build(a, mid, 2*idx)
st.build(mid+1, b, 2*idx+1)
st.tree[idx] = st.tree[2*idx] + st.tree[2*idx+1]
}
}
func (st *SegmentTree) modify(l, r, a, b, idx int) {
if l <= a && b <= r {
// 翻转 0-1
st.tree[idx] = b - a + 1 - st.tree[idx]
// 标记子节点是否要翻转
st.lazyTree[idx] = !st.lazyTree[idx]
return
}
// [a, b] 与目标区间 [l, r] 没有交集，直接返回
if b < l || a > r {
return
}
st.pushDown(a, b, idx)
mid := a + (b-a)/2
if mid >= l {
st.modify(l, r, a, mid, 2*idx)
}
if mid+1 <= r {
st.modify(l, r, mid+1, b, 2*idx+1)
}
st.tree[idx] = st.tree[2*idx] + st.tree[2*idx+1]
}
func (st *SegmentTree) query(l, r, a, b, idx int) int {
if l <= a && b <= r {
return st.tree[idx]
}
if b < l || a > r {
return 0
}
st.pushDown(a, b, idx)
mid := a + (b-a)/2
res := 0
if mid >= l {
res += st.query(l, r, a, mid, 2*idx)
}
if mid+1 <= r {
res += st.query(l, r, mid+1, b, 2*idx+1)
}
return res
// return st.query(l, r, a, mid, 2*idx) + st.query(l, r, mid+1, b, 2*idx+1)
}
func (st *SegmentTree) pushDown(a, b, idx int) {
if st.lazyTree[idx] {
mid := a + (b-a)/2
st.tree[2*idx] = mid - a + 1 - st.tree[2*idx]
st.lazyTree[2*idx] = !st.lazyTree[2*idx]
st.tree[2*idx+1] = b - mid - st.tree[2*idx+1]
st.lazyTree[2*idx+1] = !st.lazyTree[2*idx+1]
st.lazyTree[idx] = false
}
}
func handleQuery(nums1 []int, nums2 []int, queries [][]int) []int64 {
var sum int64
for _, num := range nums2 {
sum += int64(num)
}
sTree := NewSegmentTree(nums1)
var ans []int64
for _, query := range queries {
if query[0] == 1 {
l, r := query[1], query[2]
sTree.ReverseRange(l, r)
} else if query[0] == 2 {
p := query[1]
fmt.Println()
sum += int64(sTree.SumRange(0, len(nums1)-1)) * int64(p)
} else {
ans = append(ans, sum)
}
}
return ans
}
|
