# C

# 题目大意

给你 $n$ 个数 $a_1, ..., a_n$ ，找到满足 $j-i = a_i + a_j~(i < j)$ 的 $(i,j)$ 的个数

# 数据范围

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

# 题解

变换原式为 $a_i+i = j - a_j$ ，维护一个 map<int, int> 记录已经有的 $a_i + i$ ，对于每次新的 $j$ ，累加即可

C++

void solve () {
    cin >> n, a = vector<int>(n + 1);
    int res = 0;
    for (int i = 1; i <= n; i++)
        cin >> a[i], res += ii[i - a[i]], ii[a[i] + i]++;
    cout << res << '\n';
}

# D

# 题目大意

你将收到 $n$ 份礼物，你有一个情绪值 $val$ ，非负整数。每收到一份礼物，你的情绪值会发生变化，每份礼物有价值 $P$ 、情绪上升度 $A$ 、情绪下降度 $B$

当前礼物的 $P \ge val$ 时， $val += A$
当前礼物的 $P < val$ 时， $val = max(0, val - B)$

现在有 $Q$ 个询问，在第 $i$ 个询问中，给定一个非负整数 $X$ ，请问若最初 $val = x$ ，收到所有礼物之后， $val$ 是多少

# 数据范围

$1 \le n \le 10^4$
$1 \le A_i, B_i, P_i \le 500$
$1 \le Q \le 5 \times 10^5$
$0 \le X \le 10^9$

# 题解

这是一道 $DP$ 题，本题重要的是要发现 $1 \le A_i,B_i,P_i \le 500$ 这个关键条件

如果一开始的情绪值很大，那么就会一直减
否则则会在 $\le 1000$ $\leq 1000$ 的范围变化，为什么？
- 如果 $val > 500$ ，那么一定会减少
- 如果 $val \le 500$ ，那么就算会增加，也不会超过 $1000$

我们不妨对 $1000$ 以内的情况去做 $DP$

状态变量： $dp_{i,j}$ 代表从第 $i$ 件礼物开始，开始收礼物的 $val$ 是 $j$ ，的最终的心情
转移方程
- 如果 $j > P_i$ ，代表下一步心情得减，dp_{i,j}=dp_
- 如果 $j \le P_i$ ，代表下一步心情得加，dp_{i,j}=dp_
倒着 $DP$

然后通过前缀和维护一个 $b$ 的 $pre$ 数组，用二分去找，我初步给出的 $val$ 从那个下标开始，会进入 $1000$ 以内，然后直接用 $DP$ 的值

C++

void solve () {
    cin >> n;
    p = vector<int>(n + 10), a = vector<int>(n + 10), b = vector<int>(n + 10), pre = vector<int>(n + 1);
    dp = vector<vector<int>>(n + 10, vector<int>(1010));

    for (int i = 1; i <= n; i++)
        cin >> p[i] >> a[i] >> b[i];
    
    for (int j = 0; j <= 1000; j++)
        dp[n + 1][j] = j;
    
    for (int i = n; i >= 1; i--)
        for (int j = 0; j <= 1000; j++)
            dp[i][j] = dp[i + 1][(j > p[i] ? max((int)0, j - b[i]) : j + a[i])];
    
    for (int i = 1; i <= n; i++)
        pre[i] = pre[i - 1] + b[i];

    cin >> q;
    while (q--) {
        cin >> x;
        if (x - 1000 > pre[n])
            cout << x - pre[n] << '\n';
        else if (x <= 1000)
            cout << dp[1][x] << '\n';
        else {
            int idx = lower_bound(pre.begin() + 1, pre.begin() + n + 1, x - 1000) - pre.begin();
            cout << dp[idx + 1][x - pre[idx]] << '\n';
        }
    }
}

前缀和二分 DFS ABC DP 排序差分

# C

# 题目大意

# 数据范围

# 题解

# D

# 题目大意

# 数据范围

# 题解

ABC-416

ABC-418