For problem statement at 1000-1999/1900-1999/1920-1929/1928/problemF.txt this is a correct solution, but verifier at 1000-1999/1900-1999/1920-1929/1928/verifierF.go ends with OK can you fix the verifier? ```go
package main
import (
"bufio"
"fmt"
"os"
"strconv"
)
type Fenwick struct {
count []int64
sum []int64
v1 []int64
v2 []int64
n int
}
func NewFenwick(n int) *Fenwick {
return &Fenwick{
count: make([]int64, n+1),
sum: make([]int64, n+1),
v1: make([]int64, n+1),
v2: make([]int64, n+1),
n: n,
}
}
func (fw *Fenwick) Add(L int, sign int64) {
if L <= 0 {
return
}
c := sign
s := sign * int64(L)
v1 := sign * int64(L) * int64(L+1) / 2
v2 := sign * int64(L) * int64(L-1) * int64(L+1) / 6
for i := L; i <= fw.n; i += i & -i {
fw.count[i] += c
fw.sum[i] += s
fw.v1[i] += v1
fw.v2[i] += v2
}
}
func (fw *Fenwick) QueryLess(L int) (int64, int64, int64, int64) {
var c, s, v1, v2 int64
for i := L; i > 0; i -= i & -i {
c += fw.count[i]
s += fw.sum[i]
v1 += fw.v1[i]
v2 += fw.v2[i]
}
return c, s, v1, v2
}
func (fw *Fenwick) QueryTotal() (int64, int64, int64, int64) {
return fw.QueryLess(fw.n)
}
func (fw *Fenwick) QueryContribution(L int) int64 {
if L <= 0 {
return 0
}
cL, sL, v1L, v2L := fw.QueryLess(L - 1)
cT, sT, _, _ := fw.QueryTotal()
Q0 := cT - cL
Q1 := sT - sL
Qv1 := v1L
Qv2 := v2L
v1_L := int64(L) * int64(L+1) / 2
v2_L := int64(L) * int64(L-1) * int64(L+1) / 6
return Q1*v1_L - Q0*v2_L + Qv1*int64(L) - Qv2
}
type SegTree struct {
tree []int
n int
}
func NewSegTree(n int) *SegTree {
if n == 0 {
return &SegTree{
tree: []int{},
n: 0,
}
}
st := &SegTree{
tree: make([]int, 4*n),
n: n,
}
st.build(1, 0, n-1)
return st
}
func (st *SegTree) build(node, l, r int) {
st.tree[node] = r - l + 1
if l == r {
return
}
mid := (l + r) / 2
st.build(2*node, l, mid)
st.build(2*node+1, mid+1, r)
}
func (st *SegTree) Update(l, r, idx, val int) {
st.update(1, l, r, idx, val)
}
func (st *SegTree) update(node, l, r, idx, val int) {
if l == r {
if val == 1 {
st.tree[node] = 0
} else {
st.tree[node] = 1
}
return
}
mid := (l + r) / 2
if idx <= mid {
st.update(2*node, l, mid, idx, val)
} else {
st.update(2*node+1, mid+1, r, idx, val)
}
st.tree[node] = st.tree[2*node] + st.tree[2*node+1]
}
func (st *SegTree) FindFirst0(l, r, ql, qr int) int {
if ql > qr {
return -1
}
return st.findFirst0(1, l, r, ql, qr)
}
func (st *SegTree) findFirst0(node, l, r, ql, qr int) int {
if ql > r || qr < l || st.tree[node] == 0 {
return -1
}
if l == r {
return l
}
mid := (l + r) / 2
res := st.findFirst0(2*node, l, mid, ql, qr)
if res != -1 {
return res
}
return st.findFirst0(2*node+1, mid+1, r, ql, qr)
}
func (st *SegTree) FindLast0(l, r, ql, qr int) int {
if ql > qr {
return -1
}
return st.findLast0(1, l, r, ql, qr)
}
func (st *SegTree) findLast0(node, l, r, ql, qr int) int {
if ql > r || qr < l || st.tree[node] == 0 {
return -1
}
if l == r {
return l
}
mid := (l + r) / 2
res := st.findLast0(2*node+1, mid+1, r, ql, qr)
if res != -1 {
return res
}
return st.findLast0(2*node, l, mid, ql, qr)
}
func main() {
scanner := bufio.NewScanner(os.Stdin)
scanner.Split(bufio.ScanWords)
scanner.Buffer(make([]byte, 1024*1024), 1024*1024*64)
scanInt := func() int {
scanner.Scan()
res, _ := strconv.Atoi(scanner.Text())
return res
}
scanInt64 := func() int64 {
scanner.Scan()
res, _ := strconv.ParseInt(scanner.Text(), 10, 64)
return res
}
n := scanInt()
m := scanInt()
q := scanInt()
a := make([]int64, n)
for i := 0; i < n; i++ {
a[i] = scanInt64()
}
b := make([]int64, m)
for i := 0; i < m; i++ {
b[i] = scanInt64()
}
MAX := n
if m > MAX {
MAX = m
}
MAX += 5
fwA := NewFenwick(MAX)
fwB := NewFenwick(MAX)
stA := NewSegTree(n - 1)
stB := NewSegTree(m - 1)
A := make([]int, n-1)
B := make([]int, m-1)
D_a := make([]int64, n-1)
D_b := make([]int64, m-1)
total_ans := int64(n) * int64(m)
updateA := func(i int, new_val int) {
if A[i] == new_val {
return
}
if new_val == 1 {
L_idx := stA.FindLast0(0, n-2, 0, i-1)
if L_idx == -1 {
L_idx = -1
}
lenL := i - 1 - L_idx
R_idx := stA.FindFirst0(0, n-2, i+1, n-2)
if R_idx == -1 {
R_idx = n - 1
}
lenR := R_idx - (i + 1)
if lenL > 0 {
fwA.Add(lenL, -1)
total_ans -= fwB.QueryContribution(lenL)
}
if lenR > 0 {
fwA.Add(lenR, -1)
total_ans -= fwB.QueryContribution(lenR)
}
new_len := lenL + 1 + lenR
fwA.Add(new_len, 1)
total_ans += fwB.QueryContribution(new_len)
stA.Update(0, n-2, i, 1)
A[i] = 1
} else {
L_idx := stA.FindLast0(0, n-2, 0, i-1)
if L_idx == -1 {
L_idx = -1
}
lenL := i - 1 - L_idx
R_idx := stA.FindFirst0(0, n-2, i+1, n-2)
if R_idx == -1 {
R_idx = n - 1
}
lenR := R_idx - (i + 1)
old_len := lenL + 1 + lenR
fwA.Add(old_len, -1)
total_ans -= fwB.QueryContribution(old_len)
if lenL > 0 {
fwA.Add(lenL, 1)
total_ans += fwB.QueryContribution(lenL)
}
if lenR > 0 {
fwA.Add(lenR, 1)
total_ans += fwB.QueryContribution(lenR)
}
stA.Update(0, n-2, i, 0)
A[i] = 0
}
}
updateB := func(i int, new_val int) {
if B[i] == new_val {
return
}
if new_val == 1 {
L_idx := stB.FindLast0(0, m-2, 0, i-1)
if L_idx == -1 {
L_idx = -1
}
lenL := i - 1 - L_idx
R_idx := stB.FindFirst0(0, m-2, i+1, m-2)
if R_idx == -1 {
R_idx = m - 1
}
lenR := R_idx - (i + 1)
if lenL > 0 {
fwB.Add(lenL, -1)
total_ans -= fwA.QueryContribution(lenL)
}
if lenR > 0 {
fwB.Add(lenR, -1)
total_ans -= fwA.QueryContribution(lenR)
}
new_len := lenL + 1 + lenR
fwB.Add(new_len, 1)
total_ans += fwA.QueryContribution(new_len)
stB.Update(0, m-2, i, 1)
B[i] = 1
} else {
L_idx := stB.FindLast0(0, m-2, 0, i-1)
if L_idx == -1 {
L_idx = -1
}
lenL := i - 1 - L_idx
R_idx := stB.FindFirst0(0, m-2, i+1, m-2)
if R_idx == -1 {
R_idx = m - 1
}
lenR := R_idx - (i + 1)
old_len := lenL + 1 + lenR
fwB.Add(old_len, -1)
total_ans -= fwA.QueryContribution(old_len)
if lenL > 0 {
fwB.Add(lenL, 1)
total_ans += fwA.QueryContribution(lenL)
}
if lenR > 0 {
fwB.Add(lenR, 1)
total_ans += fwA.QueryContribution(lenR)
}
stB.Update(0, m-2, i, 0)
B[i] = 0
}
}
for i := 0; i < n-1; i++ {
D_a[i] = a[i] - a[i+1]
if D_a[i] != 0 {
updateA(i, 1)
}
}
for i := 0; i < m-1; i++ {
D_b[i] = b[i] - b[i+1]
if D_b[i] != 0 {
updateB(i, 1)
}
}
writer := bufio.NewWriter(os.Stdout)
defer writer.Flush()
fmt.Fprintln(writer, total_ans)
for i := 0; i < q; i++ {
t := scanInt()
l := scanInt()
r := scanInt()
x := scanInt64()
if t == 1 {
l -= 1
r -= 1
if l > 0 {
idx := l - 1
D_a[idx] -= x
new_val := 0
if D_a[idx] != 0 {
new_val = 1
}
updateA(idx, new_val)
}
if r < n-1 {
idx := r
D_a[idx] += x
new_val := 0
if D_a[idx] != 0 {
new_val = 1
}
updateA(idx, new_val)
}
} else {
l -= 1
r -= 1
if l > 0 {
idx := l - 1
D_b[idx] -= x
new_val := 0
if D_b[idx] != 0 {
new_val = 1
}
updateB(idx, new_val)
}
if r < m-1 {
idx := r
D_b[idx] += x
new_val := 0
if D_b[idx] != 0 {
new_val = 1
}
updateB(idx, new_val)
}
}
fmt.Fprintln(writer, total_ans)
}
}
```