link：https://codeforces.com/contest/1969/problem/E
给一序列 \(a\)，要使得 \(a\) 的任意子段 \([a_l,\dots,a_r]\) 都存在某数 \(a_i\)，使得其只在该子段恰出现一次。问最少修改 \(a\) 中几处位置？
\(1\leq n\leq 3\times 10^5\).
一个不太好的想法：对每个值去考虑，这样的入手点只考虑了局部的某个值，而无法联系上整个序列这一整体结构。
这个问题应该抓的重点是其整体结构：假设 \([a_1,\dots,a_i]\) 的所有子段都满足条件，考虑加入一个 \(a_{i+1}\) 产生的的影响，只需考虑所有以 \(i+1\) 为右端点的区间是否仅含一个数。
那么很自然地考察这些后缀区间，所有以 \(i\) 为右端点的区间，如果因为在结尾拼上了一个 \(a_{i+1}\) 而“变坏了”，那罪魁祸首只可能是 \(a_{i+1}\) 它和之前某个数（不妨称其为 \(a_j\) ）重复了，并且\(a_j\)是作为 \([j,i+1]\) 中唯一一个仅出现一次的数。
好，那现在就是怎么快速判断它的问题，一个自然的想法是在这时候对每个值考虑：一个值出现1次到出现2次是质变，而2次以上其实我们并不关心，因此如果动态地对每个值打个记号，在最后一次出现的位置打上 +1，倒数第二次出现的位置打 -1，更前的位置全部打 0，记录这样一个序列 \([s_1,\dots,s_n]\)，那么就变成判断，是否存在某个 \([s_l,\dots,s_{i+1}]\) 的和为0。
考虑设 \(f_i=\sum_{j=i}^n s_j\) 这样一个后缀和，那么判断的是 \(\min(f_1,\dots,f_{i+1})>0\)，而对于插入 \(a_{i+1}\) 而言，意味着修改 \(s_{i+1}\)，也就是对所有 \(f_1,\dots,f_{i+1}\) 做一个区间修改，所以就是区间min-区间赋值（具体地应该是区间加）的问题，线段树可以解决：
（写的时候把 \(\min\) 打成了 \(\max\) 还调了半天T_T）
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define endl '\n'
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
const int N=3e5+5;
const int INF=0x3f3f3f3f;
int n,a[N],s[N];
int lst[N],pst[N];
struct SegT{
#define ls (node<<1)
#define rs (node<<1|1)
int n;
int tr[N<<2],tag[N<<2];
void push_up(int node){
tr[node]=min(tr[ls],tr[rs]);
}
void push_down(int node){
if(tag[node]==0)return;
tag[ls]+=tag[node];tr[ls]+=tag[node];
tag[rs]+=tag[node];tr[rs]+=tag[node];
tag[node]=0;
}
void build(int node,int l,int r){
tr[node]=tag[node]=0;
if(l==r)return;
int mid=(l+r)>>1;
build(ls,l,mid);build(rs,mid+1,r);
}
void init(int __n){
n=__n;
build(1,1,n);
}
void add(int node,int l,int r,int ql,int qr,int v){
if(ql<=l&&r<=qr){
tag[node]+=v;
tr[node]+=v;
return;
}
push_down(node);
int mid=(l+r)>>1;
if(mid>=ql)add(ls,l,mid,ql,qr,v);
if(mid+1<=qr)add(rs,mid+1,r,ql,qr,v);
push_up(node);
}
int query(int node,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr)return tr[node];
push_down(node);
int ret=INF;
int mid=(l+r)>>1;
if(mid>=ql)ret=query(ls,l,mid,ql,qr);
if(mid+1<=qr)ret=min(ret,query(rs,mid+1,r,ql,qr));
return ret;
}
int query(int l,int r){return query(1,1,n,l,r);}
void modify(int x,int v){
add(1,1,n,1,x,-s[x]);
s[x]=v;
add(1,1,n,1,x,s[x]);
}
}tr;
int main(){
fastio;
int tc;cin>>tc;
while(tc--){
cin>>n;
rep(i,1,n)cin>>a[i];
rep(i,1,n)lst[i]=pst[i]=-1,s[i]=0;
tr.init(n);
int ans=0;
rep(i,1,n){
if(~pst[a[i]])tr.modify(pst[a[i]],0);
if(~lst[a[i]])tr.modify(lst[a[i]],-1);
tr.modify(i,1);
if(tr.query(1,i)>0){
pst[a[i]]=lst[a[i]];
lst[a[i]]=i;
continue;
}
ans++;
if(~lst[a[i]])tr.modify(lst[a[i]],1);
if(~pst[a[i]])tr.modify(pst[a[i]],-1);
}
cout<<ans<<endl;
}
return 0;
}