P5324 题解

题意

给定一个数列 \(\{a_n\}\)，定义一次删除操作为：假设当前序列长度为 \(len\)，删除序列中所有等于 \(len\) 的数。

现在有 \(m\) 个操作，每次操作为单点修改或整体加减。每次操作完后，你需要修改若干个数，使得序列能够在若干次删除操作后被删空，求最小修改次数。

数据范围：\(1 \le n, m \le 1.5 \cdot 10^5, 0 \le p \le n, 1 \le x, a_i \le n\) 。

思路

这种操作题肯定是先找出一种静态求取答案的方法，然后再用数据结构等东西维护这个答案。

那么如何求取答案呢？首先按照题意，序列里面不同元素的顺序是无关紧要的，我们只需要看每个数的出现次数即可。而知道了这一性质后该怎么办呢，蒟蒻开始罚坐。。。太菜了 QAQ 其实这是一道结论题，有结论：

假设元素 \(i\) 的出现次数为 \(cnt_i\)，将区间 \([i - cnt_i + 1, i]\) 覆盖，答案为 \([1, n]\) 中未被覆盖的点的数量。

考虑证明：

• 这一定是答案的上界，有一种构造方法是：把一些被覆盖多次的点搬到未被覆盖的位置上，所以答案一定 $\le $ 这种构造方式。
• 这一定是答案的下界，因为一个点未被覆盖，说明比它大的点到不了它，这样就无法到达比它小的点，故不应存在未被覆盖的点。

于是就可以维护了，对于单点修改操作，很显然。对于整体加减操作，相当于平移 \([1, n]\) 的区间，当 \(x\) 被移出区间时，对 \([x - cnt_x + 1, x]\) 进行区间减一，加进来时区间加一即可。可以用线段树维护最小值和最小值出现次数，时间复杂度 \(O(n \log n)\)。代码稍微有点细节：

#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = l; i <= r; ++i)
#define per(i, r, l) for (int i = r; i >= l; --i)
#define re(i, n) for (int i = 0; i < n; ++i)
#define pe(i, n) for (int i = n - 1; i >= 0; --i)
using namespace std;
using i64 = long long;
const int N = 9E5 + 5;
int n, m, a[N], L = 3E5;
int cnt[N];
struct segt {
    int tag[N << 2];
    struct node {
        int mn = 1E9;
        int cnt = 0;
    } t[N << 2];
    friend node operator+(node a, node b) {
        node c;
        c.mn = min(a.mn, b.mn);
        if (a.mn == c.mn) c.cnt += a.cnt;
        if (b.mn == c.mn) c.cnt += b.cnt;
        return c;
    }
    void pull(int x) {t[x] = t[x * 2] + t[x * 2 + 1];}
    void build(int x, int l, int r) {
        tag[x] = 0;
        if (l == r) {t[x].cnt = 1; t[x].mn = 0; return ;}
        int mid = (l + r) / 2;
        build(x * 2, l, mid);
        build(x * 2 + 1, mid + 1, r);
        pull(x);
    }
    void apply(int x, int val) {tag[x] += val; t[x].mn += val;}
    void push(int x) {
        apply(x * 2, tag[x]);
        apply(x * 2 + 1, tag[x]);
        tag[x] = 0;
    }
    void modify(int x, int l, int r, int L, int R, int val) {
        if (r < L || l > R) return ;
        if (l >= L && r <= R) return apply(x, val);
        int mid = (l + r) / 2; push(x);
        modify(x * 2, l, mid, L, R, val);
        modify(x * 2 + 1, mid + 1, r, L, R, val);
        pull(x);
    }
    void modify(int l, int r, int val) {
        modify(1, 1, 3 * L, l, r, val);
    }
    void modify(int pos, int val) {modify(pos, pos, val);}
    node query(int x, int l, int r, int L, int R) {
        if (r < L || l > R) return {};
        if (l >= L && r <= R) return t[x];
        int mid = (l + r) / 2; push(x);
        return query(x * 2, l, mid, L, R) + query(x * 2 + 1, mid + 1, r, L, R);
    }
    int query(int l, int r) {
        auto temp = query(1, 1, 3 * L, l, r);
        if (temp.mn != 0) return 0;
        return temp.cnt;
    }
} t;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    t.build(1, 1, 3 * L);
    rep(i, 1, n) cin >> a[i], ++cnt[a[i] + L];
    rep(i, L + 1, L + n) if (cnt[i]) t.modify(i - cnt[i] + 1, i, 1);
    int tag = 0; while (m--) {
        int p, x; cin >> p >> x;
        if (p) {
            if (a[p] >= 1 - tag && a[p] <= n - tag)
                t.modify(a[p] + L - cnt[a[p] + L] + 1, -1);
            --cnt[a[p] + L];
            a[p] = x - tag;
            if (a[p] >= 1 - tag && a[p] <= n - tag)
                t.modify(a[p] + L - cnt[a[p] + L], 1);
            ++cnt[a[p] + L];
        } else {
            #define modi(pos, val) t.modify(L + pos - cnt[pos + L] + 1, L + pos, val) 
            if (x > 0 && cnt[n - tag + L]) modi((n - tag), -1);
            if (x < 0 && cnt[1 - tag + L]) modi((1 - tag), -1);
            tag += x;
            if (x > 0 && cnt[1 - tag + L]) modi((1 - tag), 1);
            if (x < 0 && cnt[n - tag + L]) modi((n - tag), 1);
        }
        cout << t.query(L + 1 - tag, L + n - tag) << '\n';
    }
}

这道题启发我们，做结论题时，可以多考虑答案的下界和上界都取在哪些值上，从而发现关键结论或方法。