倍增前缀和

前置知识$倍增$https://oi-wiki.org/basic/binary-lifting/ $\\$ 题目给出的是一个类似于内向基环树的图，根据对于每个$i,a[Next[i]]$跟$a[i]$关系可以建立一个边权图$\\$假设$x,y$都是正数，那么对于每次询问的最大前缀和都是走完即可,$\\$接下来就是处理负数对结局的影响.类似的我们可以利用倍增的思想额外去维护这个最大前缀和$pre$,前缀和就是$sum$,$f_{(i,j)}$代表第i给点恰好走$2^j$步,发现对于任意的区间$l,r$,$f_{(l+r).sum}$$=f_{l.sum}+f_{r.sum}$ 而最大前缀和有两种情况取$max$,从左边的序列 $l$ 贡献 $f_{(l+r).pre}=max($$f_{(l+r).pre},f_{l.pre})$和从右边的序列$r$ 贡献，因为必须是前缀需要加上左边序列的元素和 $f_{(l+r).pre}=max$$(f_{l.sum}+$$f_{r.pre},f_{(l+r).pre})$$\\$ 接下来就可以在倍增数组上维护$f_{(i,j)}$了$\\$

$f_{(i+j).sum}=$$f_{(i,j-1).sum}+f_{(f_{(i,j-1)},j-1).sum}$$\\$ $f_{(i+j).pre}=max(f_{(i+j).pre},f_{(i,j-1).pre})$$\\$ $f_{(i+j).pre}$$=max(f_{(i+j).pre},$$f_{(i,j-1).sum}+f_{(i,j-1),j-1).pre})$$\\$ 对于每次查询 $(u, k)$，输出倍增数组上查询得到的从$u$ 开始长度恰好为 $k$ 的路径的信息 $f(S).pre$ 即可$\\$ 整体时间复杂度$o(nlog_2n+qlog_2k)$$\\$

代码如下

$cpp$

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define N 200005
struct node {
	int sum, pre;
};
node merge(node a, node b) {
	return {a.sum + b.sum, max(a.pre, a.sum + b.pre)};
}
pair<int, node> f[N][30];
int n, q, x, y;
int nxt[N];
int a[N];
int u, k;
void init() {
	for (int i = 1; i <= n; i++) {
		f[i][0].first = nxt[i];
		int w;
		if (a[nxt[i]] > a[i]) {
			w = x;
		} else {
			w = y;

		}
		f[i][0].second = {w, w};
	}
	for (int i = 1; i < 30; i++) {
		for (int j = 1; j <= n; j++) {
			int v = f[j][i - 1].first;
			f[j][i] = {f[v][i - 1].first, merge(f[j][i - 1].second, f[v][i - 1].second)};
		}
	}
}
int ask(int u, int k) {
	node r = {0, 0};
	for (int i = 29; i >= 0; i--) {
		if (k >> i & 1) {
			r = merge(r, f[u][i].second);
			u = f[u][i].first;
		}
	}
	return  r.pre;
}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> q >> x >> y;
	for (int i = 1; i <= n; i++) {
		cin >> nxt[i];
	}
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	init();
	while (q--) {
		cin >> u >> k;
		cout << ask(u, k) << '\n';
	}
}

$py$

import sys


input = lambda: sys.stdin.readline().strip()

class Node:
    def __init__(self, sum=0, pre=0):
        self.sum = sum
        self.pre = pre

def merge(a, b):
    return Node(a.sum + b.sum, max(a.pre, a.sum + b.pre))

def init(n, nxt, a, x, y):
    f = [[(0, Node()) for _ in range(30)] for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        f[i][0] = (nxt[i-1], Node(x if a[nxt[i-1]-1] > a[i-1] else y, x if a[nxt[i-1]-1] > a[i-1] else y))
    
    for i in range(1, 30):
        for j in range(1, n + 1):
            v = f[j][i - 1][0]
            f[j][i] = (f[v][i - 1][0], merge(f[j][i - 1][1], f[v][i - 1][1]))
    
    return f

def ask(u, k, f):
    r = Node()
    for i in range(29, -1, -1):
        if (k >> i) & 1:
            r = merge(r, f[u][i][1])
            u = f[u][i][0]
    return r.pre

def main():
    n, q, x, y=list(map(int, input().split()))
    nxt = list(map(int, input().split()))
    a = list(map(int, input().split()))
    f = init(n, nxt, a, x, y)
    
    result = []
    for _ in range(q):
        u,k=list(map(int, input().split()))
        print(ask(u, k, f))
if __name__ == "__main__":
    main()

```

题目内容

​ 小美正在一张有向但定连通的图上玩游戏。这张图包含$n$个点，第$i$个点的权值为$a$，当小美从$i$移动到 $Next_i$时，游戏规则如下:

• 如果$aNeat_i>ai$，小美的金币将增加$x$;

• 如果$aNext_i≤ai$，小美的金币将增加$y$。

  小美会提出$q$次询问，每个询问从某个点$u$出发，移动不超过$k$步，最多能获得多少金币。

输入描述

​ 第一行输入四个整数$n,q,x,y(1≤n,q≤2×10^5,-10^6≤x,y ≤10^6)$代表图上点的数量、询问的次数、规则中金币的增加量。 ​ 第二行输入$n$个整数$Next_1,Next_z,...,Next_n(1≤ Next_i≤n)$表示第$i$个节点下一步的位置。 ​ 第三行输入$n$个整数$a_1,a_2,...,a_n(1≤a_i≤10^6)$,表示第$i$个节点的权值。 ​ 此后$q$行，每行输入两个整数$u,k(1≤u≤n,1≤k≤10^9)$ 代表一次询问的起始点和步数限制。

输出描述

对于每一次询问，在一行上输出一个整数，代表最多能获得的金币数量。

样例1

输入

4 5 -2 3
2 3 4 1
5 10 3 2
1 1
1 2
1 4
2 4
2 7

输出

0
1
4
6
8

说明

该样例如下图所示：

●对于第一次询问，走一步会扣除$2$金币，但是可以选择站在原地不走; ●对于第二次询问，走一步时金币数量减至$-2$，走两步金币数量变更为$-2+3=1$。

​

样例2

输入

4 4 2 -1
2 3 1 4
1 2 3 1000000
1 3
3 3
2 2
4 1000000

输出

4
3