「Good Subarrays」Solution

简述题意

我们定义一个数组 $b$ 是好的当且仅当所有的 $b_i\ge i$。
现在给你 $q$ 次操作，每次操作有两个数 $p$ 和 $x$，求出把 $a_p$ 赋值成 $x$ 后 $a$ 数组好的子序列的个数，每次操作独立。

• $1\le n,q\le 2\times 10^5$，$1\le a_i,p_j,x_j\le n$。

思路

首先考虑 $\text{Easy Version}$ 怎么做。

由于没有修改，求子序列的个数问题，一般都是从长度和端点入手。对于此题，考虑求出以 $i$ 为开头的满足条件的子序列个数。

注意到，某个元素在子序列和原序列中的下标位置并不一样，所以很难处理。考虑令 $c_i=a_i-i$（算是一个 $\text{Trick}$ 吧），那么，对于在原序列中的 $[l,r]$，其满足条件就等价于：

$$\forall i\in [l,r],c_i+(l-1)\ge 0$$

即

i ∈ [ l , r ] ， m i n { c i } + ( l − 1 ) ≥ 0 i \in [l,r]，\mathrm{min\{c_i\}}+(l-1) \ge 0 i∈[l,r]，min{ci​}+(l−1)≥0

由于最小值满足单调性，所以当左端点固定时，右端点一定单调，二分求解即可，下令 $ans$ 表示未修改时 $a$ 中满足条件的子序列个数。

再考虑修改，对于每个 $i$，我们都可以求出一个 $r_i,R_i$，$r_i$ 表示对于 $\forall r\in [i,r_i]$ 都有 $[i,r]$ 是一个合法子序列，$R_i$ 表示强制钦定 $r_i$ 满足条件，即 $a_{r_i}=inf$ 后最靠右的满足 $[i,R_i]$ 是一个合法子序列的点。

由于修改独立，且注意到修改一个点，只会对左边的点产生影响。

所以，对于每次修改 $p,x$，分成以下三种情况考虑：

• $a_p=x$，直接输出 $ans$ 即可。
• $a_p<x$，那么显然原来一些不满足条件的子序列现在可能满足条件了。对于某个 $i$，如果原来 $r_i=p-1$，那么就证明 $i$ 原来扩展右端点时在 $p$ 这个点 “卡住了”，由于这样的 $i$ 是连续的（$r_i\ge r_{i-1}$），不妨二分求出 $[l,r]$ 表示对于 $\forall i\in [l,r]$ 都满足 $r_i=p-1$。显然，只满足这个条件是不够的，还需满足 m i n { a i , a i + 1 , a i + 2 , . . . , a p − 1 , x − p } + ( i − 1 ) ≥ 0 \mathrm{min\{a_i,a_{i+1},a_{i+2},...,a_{p-1},x-p\}} + (i - 1) \ge 0 min{ai​,ai+1​,ai+2​,...,ap−1​,x−p}+(i−1)≥0 才行，然而这样的 $i$ 又是连续的（$i$ 越往左越难满足），所以不妨求出同时满足两个条件的 $i$ 区间 $[l_2,r_2]$，那么对于 $i\in [l_2,r_2]$，其对答案的贡献不再是 $r_i-i+1$，而是 $R_i-i+1$ 了，这个通过前缀和预处理在原答案的基础上更新即可。
• $a_p>x$，同理可以二分求出 $[l,r](r<i)$， 满足 $i\in [l,r],r_i\ge p$，然后在 $[l,r]$ 的基础上，二分求出 $[l_2,r_2]$， 满足 i ∈ [ l 2 , r 2 ] ， m i n { a i , a i + 1 , a i + 2 , . . . . , a p − 1 , x − p } + ( i − 1 ) < 0 i \in [l_2,r_2]，\mathrm{min\{a_i,a_{i+1},a_{i+2},....,a_{p-1},x-p\}}+(i-1) < 0 i∈[l2​,r2​]，min{ai​,ai+1​,ai+2​,....,ap−1​,x−p}+(i−1)<0，那么对于 $[l_2,r_2]$ 里面的点对答案的贡献不再是 $r_i-i+1$，而是 $(p-1)-i+1$，同理前缀和求出即可。

代码

码量并不大，但要注意一下二分的边界和一些 $[l,r]$ 或 $[l_2,r_2]$ 不存在的特殊情况。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 2e5 + 5;
int n , q , a[MAXN] , R[MAXN] , RR[MAXN] , Min[MAXN][20];
int idl[MAXN] , idr[MAXN] , pre1[MAXN] , pre2[MAXN];
int GetMin(int l , int r) {
	int s = log2(r - l + 1);
	return min(Min[l][s] , Min[r - (1 << s) + 1][s]);
}
int w(int l , int r) {return (l + r) * (r - l + 1) / 2;}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr) , cout.tie(nullptr);
	cin >> n;
	for (int i = 1 ; i <= n ; i ++) cin >> a[i] , Min[i][0] = (a[i] -= i);
	for (int j = 1 ; j <= 18 ; j ++) {
		for (int i = 1 ; i + (1 << j) - 1 <= n ; i ++) {
			Min[i][j] = min(Min[i][j - 1] , Min[i + (1 << j - 1)][j - 1]);
		}
	}
	int lst = 0;
	for (int i = 1 ; i <= n ; i ++) {
		int l = i , r = n;
		while(l < r) {
			int mid = l + r + 1 >> 1;
			if (GetMin(i , mid) + (i - 1) >= 0) l = mid;
			else r = mid - 1;
		}
		if (!idl[l]) idl[l] = i;
		idr[l] = i;
		R[i] = l , pre1[i] = pre1[i - 1] + (l - i + 1);
		l = l + 1 , r = n;
		if (l >= n) {
			RR[i] = n , pre2[i] = pre2[i - 1] + (n - i + 1);
			continue;
		}
		int ql = l + 1;
		while(l < r) {
			int mid = l + r + 1 >> 1;
			if (GetMin(ql , mid) + (i - 1) >= 0) l = mid;
			else r = mid - 1;
		}
		pre2[i] = pre2[i - 1] + (l - i + 1) , RR[i] = l;
	}
	cin >> q;
	while(q --) {
		int p , x;
		cin >> p >> x;
		x -= p;
		if (p == 1 || a[p] == x) {
			cout << pre1[n] << '\n';
			continue;
		}
		if (a[p] < x) {
			int l = idl[p - 1] , r = idr[p - 1];
			while(l < r) {
				int mid = l + r >> 1;
				if (min(GetMin(mid , p - 1) , x) + (mid - 1) >= 0) r = mid;
				else l = mid + 1;
			}
			if (min(GetMin(l , p - 1) , x) + (l - 1) < 0) cout << pre1[n] << '\n';
			else cout << pre1[n] + (pre2[idr[p - 1]] - pre2[l - 1]) - (pre1[idr[p - 1]] - pre1[l - 1]) << '\n';
		} else {
			int l = 1 , r = p - 1;
			while(l < r) {
				int mid = l + r >> 1;
				if (R[mid] >= p) r = mid;
				else l = mid + 1;
			}
			if (R[l] < p) cout << pre1[n] << '\n';
			else {
				int l2 = l , r2 = p - 1;
				while(l2 < r2) {
					int mid = l2 + r2 + 1 >> 1;
					if (min(GetMin(mid , p - 1) , x) + (mid - 1) < 0) l2 = mid;
					else r2 = mid - 1;
				}
				if (min(GetMin(l2 , p - 1) , x) + (l2 - 1) >= 0) cout << pre1[n] << '\n';
				else cout << pre1[n] - (pre1[l2] - pre1[l - 1]) + w(p - l2 , p - l) << '\n';
			}
		}
	}
	return 0;
}