题解：CF1969E Unique Array
xiezheyuan
·
·
题解
阅读本题解前，请阅读并注意区分【简要题意】中好的序列和优秀的序列的概念。
简要题意
定义一个序列是好的，当且仅当存在一个数在序列中出现且仅出现一次。定义一个序列是优秀的，当且仅当其所有非空子段都是好的。
给定一个长度为 n 的序列 a，你可以进行任意次操作，每次操作将 选定一个 a_i 修改为任意整数。你需要将 a 变成优秀的序列，输出最小操作次数。
## 思路
非常厉害的一道题目，明明每一步都很自然，为什么我想不出来？
首先我们考虑修改一个位置，一定会修改成一个不在序列中出现的数，以消除其影响。所以其实相当于在序列中选择若干个数充当断点，用这些断点分割序列（抛弃断点），则每个分割得到的段都必须是优秀的（由于断点的数是唯一的，所以跨越段的区间，一定是好的）。
根据这个题意转化，我们很容易设计一个贪心，我们从左往右扫，遇到一个点，如果到这个点的前缀不再是优秀的了，就将这个点充当断点。这个贪心的策略正确性几乎是显然的。
由于对于前缀 $[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)$。
## 代码
```cpp
#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
```