C2. Good Subarrays (Hard Version)（双指针/前缀和/组合数学）_c2. dual (hard version)

题目
参考

题意

定义长度m的数组b为good数组，如果对于1<=i<=m，有b[i]>=i。
给定长度为n的数组a。

给定m次独立的查询，对于每次查询，将a[p]修改为x，问修改后，
a存在多少区间范围为[l,r]的子数组a[l],a[l+1], … , a[r-1], a[r]，为good数组。1<=l<=r<=n，

其中1<=a[i]<=n
留意到，每次查询都是独立的，即上次对数组的修改，不会影响下一个查询的原始的a数组。

思路

预处理，双指针、前缀和。
查询前预处理下每个节点能最左和最右延伸的最远的下标位置。
以及给定一次修改机会，每个节点能向右延伸的最右位置。
同时预处理以前i个节点开始的能得到的good数组数量S1；
和给定一次修改机会，前i个节点开始的能得到的good数组数量S2；

对于每个查询。

• 如果修改的x等于原来的a[p]，则答案不变。
• 如果修改的x小于a[p]，则此时答案变小。我们要重新计算，原本可以刚好到达点p的区间。具体就是最右位置刚好到达p，但现在到不了p的若干左端点。
• 如果修改的x大于a[p]，则此时答案变大。我们要重新计算，原本可以刚好到达p-1的区间。具体就是最右位置刚好到达p-1，但现在可以到达p的若干左端点。这时可以用上了S2数组。

具体实现在代码做了详细的注释。其中第2种情况用到了排列组合。

代码

代码和思路源自
官方题解评论区 oldyan
写得非常地清晰~

#include <bits/stdc++.h>
using namespace std;

int n;
vector<int> arr, left_most, right_most, right_second_most;
void get_bound() {
    // left_most[i] represents the leftmost point such that subarray arr[left_most[i]:i] is good
    left_most.resize(n + 1);
    // right_most[i] represents the rightmost point such that subarray arr[i:right_most[i]] is good
    right_most.resize(n + 1);
    // right_second_most[i] is similar with right_most[i]
    // but when you start from i, and go right, you have one chance to skip bad point.
    right_second_most.resize(n + 1);
    for (int l = 1, r = 1, r2 = 1; l <= n; l++) {
        while (r <= n and arr[r] - r >= 1 - l) {
            left_most[r] = l;
            r++;
        }
        right_most[l] = r - 1;
        r2 = max(r2, min(r + 1, n + 1));
        while (r2 <= n and arr[r2] - r2 >= 1 - l) {
            r2++;
        }
        right_second_most[l] = r2 - 1;
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    arr.resize(n + 1);
    for (int i = 1; i <= n; i++) cin >> arr[i];
    get_bound();

    // S1: presum of contributions of all points
    // S2: presum of contributions of all points, if each of them has one skip chance.
    std::vector<long long> S1(n + 1);
    std::vector<long long> S2(n + 1);
    for (int i = 1; i <= n; i++) S1[i] = S1[i - 1] + (right_most[i] - i + 1);
    for (int i = 1; i <= n; i++) S2[i] = S2[i - 1] + (right_second_most[i] - i + 1);
    long long total = S1.back();

    int m;
    cin >> m;
    for (int i = 0; i < m; i++) {
        int p, x;
        cin >> p >> x;
        if (x == arr[p]) {
            cout << total << '\n';
        } else if (x < arr[p]) {
            int now_left_most = max(left_most[p], p - x + 1);
            if (now_left_most == left_most[p]) {
                cout << total << '\n';
                continue;
            }
            // now_left_most > left_most[p]
            // we can cut off contributions from left_most[p] to now_left_most-1.
            // but, they are not cut off completely. they can still reach p-1.
            long long cut_off = S1[now_left_most - 1] - S1[left_most[p] - 1];
            // calculation of remain.
			// case1. choose start pose L from index [left_most[p], now_left_most-1],
			// 		  choose end pose R from index [now_left_most, p-1]
			// 		(now_left_most - left_most[p]) * (p - now_left_most)
			// case2. choose start and end pose l, r from index [left_most[p], now_left_most-1]
			//		  so the total num is len * (len + 1) / 2
			//      (now_left_most - left_most[p]) * (now_left_most - left_most[p] + 1) / 2
			// case1 + case2 get the formula below: 
            long long remain = (long long)((p - now_left_most) + (p - left_most[p] + 1)) * (now_left_most - left_most[p]) / 2;
            cout << total - cut_off + remain << '\n';
        } else {
            int now_left_most = max(int(lower_bound(right_most.begin() + 1, right_most.end(), p - 1) - right_most.begin() - 1) + 1, p - x + 1);
            if (now_left_most == left_most[p]) {
                cout << total << '\n';
                continue;
            }
            // now_left_most < left_most[p]
            // this is the time to use skip chance!
            // for all those points that stuck at p, they can skip p and reach right_second_most
            long long old_sum = S1[left_most[p] - 1] - S1[now_left_most - 1];
            long long now_sum = S2[left_most[p] - 1] - S2[now_left_most - 1];
            cout << total - old_sum + now_sum << '\n';
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86