[Medium] CF1969E Unique Array

阅读本题解前，请阅读并注意区分【简要题意】中好的序列和优秀的序列的概念。

简要题意

定义一个序列是好的，当且仅当存在一个数在序列中出现且仅出现一次。定义一个序列是优秀的，当且仅当其所有非空子段都是好的。

给定一个长度为 $n$ 的序列 $a$，你可以进行任意次操作，每次操作将 选定一个 $a_i$ 修改为任意整数。你需要将 $a$ 变成优秀的序列，输出最小操作次数。

$T$ 组数据。$1\leq n,\sum n\leq 3\times 10^5,1\leq a_i\leq n$。

思路

非常厉害的一道题目，明明每一步都很自然，为什么我想不出来？

首先我们考虑修改一个位置，一定会修改成一个不在序列中出现的数，以消除其影响。所以其实相当于在序列中选择若干个数充当断点，用这些断点分割序列（抛弃断点），则每个分割得到的段都必须是优秀的（由于断点的数是唯一的，所以跨越段的区间，一定是好的）。

根据这个题意转化，我们很容易设计一个贪心，我们从左往右扫，遇到一个点，如果到这个点的前缀不再是优秀的了，就将这个点充当断点。这个贪心的策略正确性几乎是显然的。

由于对于前缀 $[1,x]$ 不再是优秀的，而 $[1,x-1]$ 是优秀的，所以一定是存在一个右端点为 $x$ 的区间不是好的。这启发我们研究哪些子段是好的。

对于每个数 $a_i$，记其前面第一个与 $a_i$ 相同的数为 $a_{\mathrm{pre}_i}$，后面第一个与 $a_i$ 相同的数为 $a_{\mathrm{nxt}_i}$，则所有左端点位于 $[\mathrm{pre}_i+1,i]$，右端点位于 $[i,\mathrm{nxt}_i-1]$ 的区间都是好的（因为包含了一个出现一次的元素 $a_i$）。

于是可以设计一个类似扫描线的过程，维护一个数据结构，支持区间加区间查询最小值，一个位置 $\geq 1$ 表示可以以这个点为左端点，那么遇到 $i$ 就将 $[\mathrm{pre}_i+1,i]$ 增加 $1$，遇到 $\mathrm{nxt}_i$ 就将这个区间减去 $1$，这是容易实现的。实现时只需要处理出 $\mathrm{pre}_i$ 即可。

时间复杂度 $O(Tn\log n)$。

代码

#include <bits/stdc++.h>
#define ls (i << 1)
#define rs (i << 1 | 1)
#define mid ((l + r) >> 1)
using namespace std;

const int N = 3e5 + 5;
int n, a[N], bkt[N], pre[N];

int t[N << 2], tag[N << 2];

void mktag(int i, int v){ tag[i] += v, t[i] += v; }
void pushdown(int i){
    if(tag[i]) mktag(ls, tag[i]), mktag(rs, tag[i]), tag[i] = 0;
}

void update(int ql, int qr, int v, int i, int l, int r){
    if(ql > qr) return;
    if(ql <= l && r <= qr) return mktag(i, v);
    pushdown(i);
    if(ql <= mid) update(ql, qr, v, ls, l, mid);
    if(mid < qr) update(ql, qr, v, rs, mid + 1, r);
    t[i] = min(t[ls], t[rs]);
}

int query(int ql, int qr, int i, int l, int r){
    if(ql > qr) return INT_MAX;
    if(ql <= l && r <= qr) return t[i];
    pushdown(i);
    int res = INT_MAX;
    if(ql <= mid) res = min(res, query(ql, qr, ls, l, mid));
    if(mid < qr) res = min(res, query(ql, qr, rs, mid + 1, r));
    return res;
}

void solve(){
    cin >> n;
    for(int i=1;i<=n;i++) cin >> a[i];
    for(int i=1;i<=n;i++) pre[i] = bkt[a[i]], bkt[a[i]] = i;
    int p = 1, ans = 0;
    for(int i=1;i<=n;i++){
        update(pre[i] + 1, i, 1, 1, 1, n);
        update(pre[pre[i]] + 1, pre[i], -1, 1, 1, n);
        if(!query(p, i, 1, 1, n)) p = i + 1, ans++;
    }
    cout << ans << '\n';
}

void clear(){
    fill(bkt + 1, bkt + n + 1, 0);
    fill(pre + 1, pre + n + 1, 0);
    fill(t + 1, t + (n << 2) + 1, 0);
    fill(tag + 1, tag + (n << 2) + 1, 0);
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int t; cin >> t;
    while(t--) solve(), clear();
    return 0;
}

// Written by xiezheyuan