Atcoder Beginer Contest 438

一些每天的感受

工作之后，才感觉到人生的虚无，感觉不管做什么事情，在百年之后都会像尘土一样消散。我自己又没有什么兴趣爱好，生活中的很多有趣的事情似乎离我很远很远，我也不知道做什么，才能让这些东西离我近一些。所以今年确立了一些事情，其中一项是这个每天刷一道算法题，不过不强制要求，欠债式也行。即使知识如流水般划过我的脑子，即使时光飞逝，我依然要尽力留住那些能让我变得更好的东西。今日是2026年的第8天，今天的任务已经完成，还欠4题

今日题目

比赛链接: ABC 438

D (2026.01.08完成)

# -*- coding: utf-8 -*-
# !/usr/bin/env python

"""
@Author : Liang2003
@Time   : 2026/1/8 01:11

https://atcoder.jp/contests/abc438/tasks/abc438_d

题意：三个数组A、B、C，求A[1..X]+B[X+1..Y]+C[Y+1..n] 的最大值，其中 1<X<Y<n

思路：对于A[1..X]+B[X+1..Y] 可以维护一个数组dp ，dp[i][0]表示指针还在A数组，还没跳到B数组的最大值，dp[i][1]表示指针已经跳到B数组的最大值

那么题目的式子就可以表示成： dp[i][1] + suf_C[i+1] 其中 2<=i and i <= n+1

"""


def main():
    n = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    C = list(map(int, input().split()))

    suf_C = [0]*(n+2)
    for i in range(n,0,-1):
        suf_C[i] = suf_C[i+1] + C[i-1]

    dp = []
    for i in range(n+1):
        dp.append([0,0])
    # 边界情况，第一个元素一定要取A
    dp[1][0] = A[0]
    dp[1][1] = 0
    for i in range(2,n+1):
        dp[i][0] = dp[i-1][0] + A[i-1]
        dp[i][1] = max(dp[i-1][0],dp[i-1][1]) +B[i-1]


    res = 0
    for i in range(2,n):
        res = max(res, dp[i][1] + suf_C[i+1])
    print(res)


if __name__ == "__main__":
    main()

E

# -*- coding: utf-8 -*-
# !/usr/bin/env python

"""
@Author : Liang2003
@Time   : 2026/1/8 23:39

https://atcoder.jp/contests/abc438/tasks/abc438_e

题意：每个人i都有一个桶i，每一时刻 第i个人会往他当前拿的桶加 i个单位的水，然后传给第A[i]个人。
询问Q次，在T[i]时刻编号为B[i]的桶有多少单位的水

思路：想了很久处理环内环外的做法，最终还是做不了，看了一个老哥的 倍增法解法，学习一下
f[i][x] 表示 i往下走 1<<x 步的位置
g[i][x] 表示 i往下走 1<<x 步积累的贡献
"""

def LII():
    return list(map(int,input().split()))

def main():
    n,q = map(int,input().split())
    A = list(map(int,input().split()))
    A = [i-1 for i in A]
    LG = 30
    f = [[0]* n for _ in range(LG)]
    g = [[0]* n for _ in range(LG)]

    for i in range(n):
        f[0][i] = A[i]
        g[0][i] = i+1

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

    for i in range(q):
        t,b = map(int,input().split())
        res = 0
        b-=1
        for j in range(0,LG):
            if (t>>j)&1:
                res += g[j][b]
                b = f[j][b]
        print(res)

if __name__ == "__main__":
    main()