CF1404C Fixed Point Removal
又一道独立做出来的 CF2300，喜。
第一步转化
第一步转化是显然的，我们记 \(b_i = i - a_i\)，于是对于一个给定的询问 \([l, r]\)，问题转化为：
从左往右扫，有多少个位置 \(i\) 满足 \(i\) 前面能删除的个数小于 \(b_i\)。
直接做是 \(O(qn)\) 的。
分组
考虑试着从右往左加数，看看我们能不能发现什么有用的性质。于是观察到每个位置其实都对应着一个能删除自己的最晚的起点，不难发现这个位置的值一定是 \(0\)。记 \(c_i\) 表示 \(i\) 的最晚起点。
现在考虑怎么求 \(c_i\)。
考虑把相邻的 \(0\) 之间的部分划分成一组（或者说一段），于是一组内的点被分成了三类：
1、可以从本组的 \(0\) 出发被删除。
2、可以从前若干组的 \(0\) 出发被删除。
3、不能被删除。
对于 \(1\) 类点和 \(3\) 类点，我们可以分组遍历进而求得 \(c_i\)。
对于 \(2\) 类点，假设 \(i\) 位于以第 \(j\) 个 \(0\) 为起点的组，记 \(sum_j\) 表示第 \(j\) 组中 \(1\) 类点的个数，\(s_i\) 表示在 \(i\) 前面有多少个本组的 \(1\) 类点。我们可以二分一个位置 \(x\)，使其恰好满足 \(sum_{x \sim j - 1} + s_i \ge b_i\)。那么 \(c_i = x\)。
现在考虑怎么维护 \(sum_i\)。
\(sum_i\) 看似是静态的，但其实每找到一个位置的 \(c_i\)，\(sum_{c_i}\) 就要 \(+1\)（很好理解）。所以顺便说一句，求 \(c_i\) 的过程的扫描顺序也必须是从左往右。
所以用树状数组支持单点修，区间查就可以了。
于是我们在 \(O(n \log^2n)\) 的时间内得到了 \(c_i\)。
查询
很经典的离线套路：因为当右端点固定时，答案一定是随着左端点减小而增大，所以我们把询问挂在左端点上，并从右往左处理这些询问。
具体的处理方法是：从右往左一组一组的处理。假设现在在第 \(i\) 组，对于一个给定的询问 \([l, r]\)，答案可以转化为：\(\sum_{j = l}^{r}{[c_j \ge i]}\)。
于是每加入一个新的组 \(i\)，就先把 \(c_j = i\) 的所有 \(j\) 加入值域树状数组中，然后就可以 \(O(\log n)\) 地回答每个询问了。
总时间复杂度 \(O(n \log^2n + q \log n)\)。
注意一共开了两个树状数组。
#include<bits/stdc++.h>
#define F(i,l,r) for(int i(l); i <= (r); ++ i)
#define G(i,r,l) for(int i(r); i >= (l); -- i)
#define pii pair<int, int>
#define mp make_pair
#define fi first
#define se second
using namespace std;
using ll = long long;
const int N = 4e5;
const int inf = 1e9;
int n, q, cnt = 0;
int R[N], L[N], a[N], b[N], c[N], ans[N], s[N], pos[N];
vector<int> g[N];
vector<pii> Q[N];
struct Tree{int sum[N], num;int lowbit(int x){return (x & -x);}void add(int x, int y){for(; x <= num; x += lowbit(x)) sum[x] += y; }int ask(int x){int ret = 0;for(; x >= 1; x -= lowbit(x)) ret += sum[x];return ret;}
}tr, sg;
void solve(int l, int r){ // 本组的0到下一组的0的前一位 ++ cnt;R[cnt] = r;L[cnt] = l;int nw = 0;F(i, l, r){if(b[i] >= 0 && b[i] <= nw){c[i] = cnt;++ nw;}s[i] = nw;pos[i] = cnt;}
}
signed main(){ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);cin >> n >> q;F(i, 1, n){cin >> a[i];b[i] = i - a[i];c[i] = inf;}int o = 0;F(i, 1, n) if(b[i] == 0){o = i;break;}if(o == 0){F(i, 1, q) cout << "0\n";return fflush(0), 0;}F(i, o + 1, n){if(b[i] == 0){solve(o, i - 1);o = i;}}solve(o, n);tr.num = cnt;F(i, 1, cnt) tr.add(i, s[R[i]]);F(i, 1, n){if(b[i] >= 0 && c[i] == inf){int l = 0, r = pos[i] + 1, mid, tmp = b[i] - s[i], tot = tr.ask(r - 2); while(l + 1 < r){mid = (l + r) / 2;int ret = tot - tr.ask(mid - 1); if(ret >= tmp) l = mid;else r = mid;}if(l != 0){c[i] = l; tr.add(l, 1);}}}F(i, 1, n) if(c[i] != inf) g[c[i]].push_back(i);F(i, 1, q){int x, y;cin >> x >> y;Q[x + 1].push_back(mp(i, n - y));}sg.num = n;G(i, cnt, 1){for(auto j : g[i]) sg.add(j, 1);int l, r;if(i > 1){l = L[i - 1] + 1;r = R[i - 1] + 1;}else{l = 1;r = L[i];}F(j, l, r){for(auto v : Q[j]){ans[v.fi] = sg.ask(v.se);}}} F(i, 1, q) cout << ans[i] << '\n';return fflush(0), 0;
}