# D

# 题目大意

这是一道我蠢的没边的题目
给定 $(a_1, \ldots, a_n), \quad (b_1, \ldots, b_n), \quad (c_1, \ldots, c_n)$ ，求

$\max_{1 \le x < y < n} (\sum\limits_{i = 1}^{x} a_i + \sum\limits_{i = x + 1}^{y} b_i + \sum\limits_{i = y + 1}^{n} c_i)$

# 数据范围

$1 \le n \le 3 \times 10^5$

# 题解

显然，所求的式子等价于 # preA[x] + preB[y] - preB[x] + preC[n] - preC[y] ，变型有 preA[x] - preB[x] + preB[y] - preC[y] + preC[n]
那么我们不就可以枚举 $x$ ，然后求 $\max\limits_{x + 1 \le y < n} preB_y - preC_y$ 吗
这个时候，蠢得没边的我，写出了~~线段树~~

python

MAXXX = 10**30

class SegTree:
    def __init__(self, data):
        self.n = len(data)
        self.tree = [0] * (4 * self.n)
        self.build(data, 1, 0, self.n - 1)
    
    def build(self, data, node, l, r):
        if l == r:
            self.tree[node] = data[l]
        else:
            mid = (l + r) // 2
            self.build(data, node * 2, l, mid)
            self.build(data, node * 2 + 1, mid + 1, r)
            self.tree[node] = max(self.tree[node * 2], self.tree[node * 2 + 1])

    def query(self, ql, qr, node, l, r):
        if ql > r or qr < l:
            return -MAXXX
        
        if ql <= l and r <= qr:
            return self.tree[node]
        
        mid = (l + r) // 2

        return max(self.query(ql, qr, node * 2, l, mid), self.query(ql, qr, node * 2 + 1, mid + 1, r))

n = int(input())
a = [0] + list(map(int, input().split()))
b = [0] + list(map(int, input().split()))
c = [0] + list(map(int, input().split()))

preA = [0 for _ in range(n + 1)]
preB = [0 for _ in range(n + 1)]
preC = [0 for _ in range(n + 1)]
sub1 = [0 for _ in range(n + 1)]
sub2 = [0 for _ in range(n + 1)]

for i in range(1, n + 1):
    preA[i] = preA[i - 1] + a[i]
for i in range(1, n + 1):
    preB[i] = preB[i - 1] + b[i]
    sub1[i] = preA[i] - preB[i]
for i in range(1, n + 1):
    preC[i] = preC[i - 1] + c[i]
    sub2[i] = preB[i] - preC[i]

segTree = SegTree(sub2)

res = -MAXXX

for x in range(1, n - 1):
    ans = sub1[x]
    # 再去获得 max_{i = x + 1 -> i = n - 1}  sub2[i]

    res = max(res, sub1[x] + segTree.query(x + 1, n - 1, 1, 0, segTree.n - 1))

print(res + preC[n])

不能说唐完了，只能说没救了

显然，我们可以维护 sufMax ，去求

$\max\limits_{x + 1 \le y < n} preB_y - preC_y$

需要注意的是， $y \in [x + 1, n)$ ，所以，我们不能从 $n$ 开始维护 $sufMax$ ，得从 $n - 1$ 开始

python

MAXXX = 10**30

n = int(input())
a = [0] + list(map(int, input().split()))
b = [0] + list(map(int, input().split()))
c = [0] + list(map(int, input().split()))

preA = [0 for _ in range(n + 1)]
preB = [0 for _ in range(n + 1)]
preC = [0 for _ in range(n + 1)]
sub1 = [0 for _ in range(n + 1)]
sub2 = [0 for _ in range(n + 1)]
sufMax = [-MAXXX for _ in range(n + 10)]

for i in range(1, n + 1):
    preA[i] = preA[i - 1] + a[i]
for i in range(1, n + 1):
    preB[i] = preB[i - 1] + b[i]
    sub1[i] = preA[i] - preB[i]
for i in range(1, n + 1):
    preC[i] = preC[i - 1] + c[i]
    sub2[i] = preB[i] - preC[i]

for i in range(n - 1, 0, -1):
    sufMax[i] = max(sufMax[i + 1], sub2[i])

res = -MAXXX

for x in range(1, n - 1):
    ans = sub1[x]
    res = max(res, sub1[x] + sufMax[x + 1])

print(res + preC[n])

# E

# 题目大意

$n$ 个人有 $n$ 个水桶（水桶编号 $1 \to n$ ），初始时水桶均为空，有一个数组 $A = (a_1, \ldots, a_n)$ ，代表第 $i$ 个人会把水桶给 $a_i$ 人
现在，进行 $10^9$ 次操作，每次操作， $i$ 号人会给手中所有水桶添加 $i$ 的水，添加后给 $a_i$ 号人

有 $q$ 个询问，每次询问，问 $x$ 号水桶，在 $y$ 次操作后，有多少水

# 数据范围

$2 \le n \le 2 \times 10^5$
$1 \le q \le 2 \times 10^5$

# 题解

第 $i$ 个桶，第一次操作后，会在 $a_i$ 手上，第二次操作后会在 $a_{a_i}$ 手上 $\ldots$
倍增

$f_{i,j}$ 表示水桶 $i$ 在 $2^j$ 次操作后，会在谁的手上
$sum_{i,j}$ 表示水桶 $i$ 在 $2^j$ 次操作后，有多少水
转移方程为
f[i, j] = f[f[i][j - 1], j - 1]
第 $i$ 号桶传 $2^{j - 1}$ 步到了 $f_{i, j - 1}$ ，再传 $2^{j-1}$ 步，到了 f_

sum[i, j] = sum[i, j - 1] + sum[f[i][j - 1], j - 1]
第 $i$ 号桶，在传 $2^{j-1}$ 步后的水，加上第 $i$ 号桶传 $2^{j-1}$ 步后到的位置（ $f_{i, j-1}$ ）再传 $2^{j-1}$ 步后的水

初始化

水桶 $i$ 在 $2^0 = 1$ 次操作后，在 $a_i$ 手上， $f_{i, 0} = a_i$
水桶 $i$ 传 $2^0 = 1$ 次后，有 $i$ 的水， $sum_{i, 0} = i$

python

n, q = list(map(int, input().split()))
a = [0] + list(map(int, input().split()))

f = [[0 for j in range(31)] for i in range(n + 10)]
sum = [[0 for j in range(31)] for i in range(n + 10)]

for i in range(1, n + 1):
    f[i][0] = a[i]
    sum[i][0] = i

for j in range(1, 31):
    for i in range(1, n + 1):
        f[i][j] = f[f[i][j - 1]][j - 1]
        sum[i][j] = sum[i][j - 1] + sum[f[i][j - 1]][j - 1]

for i in range(q):
    t, b = list(map(int, input().split()))   # b 号 传 t 次

    res = 0

    for j in range(30, -1, -1):
        num = (1 << j)

        if num <= t:
            res += sum[b][j]
            b = f[b][j]
            t -= num
    
    print(res)

# D

# 题目大意

# 数据范围

# 题解

# E

# 题目大意

# 数据范围

# 题解

ABC-439