CF1404C Fixed Point Removal 题解

题意：

令 \(a_1, \ldots, a_n\) 为一个包含 \(n\) 个正整数的数组。

在一次操作中，你可以选择一个位置 \(i\) 使得 \(a_i = i\)，并从数组中移除 \(a_i\)（移除后，剩余部分被拼接起来）。

\(a\) 的权重定义为你能移除的最大元素数量。

你必须回答 \(q\) 个独立的查询 \((x, y)\)：在将 \(a\) 的前 \(x\) 个元素和最后 \(y\) 个元素替换为 \(n+1\)（使它们无法被移除）后，\(a\) 的权重是多少？

输入格式：

第一行包含两个整数 \(n\) 和 \(q\) \((1 \le n, q \le 3 \cdot 10^5)\)——数组的长度和查询的数量。

第二行包含 \(n\) 个整数 \(a_1\), \(a_2\), ..., \(a_n\) \((1 \leq a_i \leq n)\)——数组的元素。

接下来的 \(q\) 行中的第 \(i\) 行包含两个整数 \(x\) 和 \(y\) \((x, y \ge 0\) 且 \(x+y < n)\)。

输出格式：

打印 \(q\) 行，第 \(i\) 行应该包含一个单独的整数——第 \(i\) 个查询的答案。

考虑令 \(a_i = i - a_i\) ，这样就只保留了相对距离。

可以发现，当 \(a_i \ge 0\) 且前面被删掉的数的个数 \(\ge a_i\) 时， \(a_i\) 总能被删掉。

于是我们不需要考虑一个可以删除的序列的删除顺序了。

然而询问并不从序列的开头开始，而是询问一个区间的答案，不过看上去不是很好在线维护。（反正我不会）

考虑离线询问，将询问按右端点顺序排序。每考虑一个新的数 \(a_r\) 时，维护 \(f_i\) 表示以 \(i\) 为起点时能删掉的数。

考察 \(a_r\) 的贡献：显然 \(f_i\) 单调递减，设 \(p\) 为最大的满足 \(f_p \ge a_r\) 的位置，则 \(1\) 到 \(p\) 的每个 \(f\) 都能吃到 \(1\) 的贡献

于是我们只需要快速找到这个 \(p\) 即可，考虑用树状数组维护。

注意到每次修改时都是 \(t_1\) 加 \(1\) ，\(t_{p+1}\) 减 \(1\) ，于是我们可以直接维护每个位置减 \(1\) 的个数。

那么如何找到 \(p+1\) 呢？设当前一共加了 \(r-1\) 次，那么减的次数不会超过 \(r-1-a_r\) 次。

考虑树状数组上二分求第 \(k\) 小（全局），方式和线段树上二分挺类似的，详见代码。

时间复杂度 \(\mathcal{O}(n \log n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(3e5 + 15))

int n, a[N], tr[N], ans[N];
struct node { int x, y, id; } b[N];
int lowbit(int x) { return x & (-x); }
void add(int x, int v) { for(int i = x; i <= n; i += lowbit(i)) tr[i] += v; }
int sum(int x, int r = 0) { for(int i = x; i; i -= lowbit(i)) r += tr[i]; return r; }
int kth(int k)
{
    int p = 0;
    for(int i = 1 << 18; i; i >>= 1)
        if(p + i <= n && k - tr[p + i] > 0) { p += i; k -= tr[p]; }
    return p + 1;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int m; cin >> n >> m;
    for(int i = 1; i <= n; i++) { cin >> a[i]; a[i] = i - a[i]; }
    for(int i = 0; i < m; i++)
    {
        cin >> b[i].x >> b[i].y;
        b[i].x = 1 + b[i].x; b[i].y = n - b[i].y; b[i].id = i;
    }
    sort(b, b + m, [](node a, node b) { return a.y < b.y; });
    int pos = 1;
    for(int i = 0; i < m; i++)
    {
        for(int k; pos <= b[i].y; ++pos) {
            k = (a[pos] < 0 ? 1 : min(kth(pos - a[pos]), pos + 1)); add(k, 1);
        }
        ans[b[i].id] = b[i].y - sum(b[i].x);
    }
    for(int i = 0; i < m; i++) cout << ans[i] << '\n';
    return 0;
}