题解：CF1969E Unique Array

· · 题解

本篇题解提供一种扫描线的角度，但实质上与维护区间最小值的做法相近。

P5490 【模板】扫描线 & 矩形面积并

思路

首先，以 l 为横轴 r 为纵轴建立平面直角坐标系，再对于所有的子区间 [l,r](1\le l\le r\le n) ，将之对应于坐标系中左下角为 (l-1,r-1) 右上角 (l,r) 的小正方形，其分布应如下图。

接着，由题意，对于序列中的一个下标 i 及其对应的数 a_i，设pre_i=\max(\{j|j<i\land a_i=a_j\}\cup\{0\}) ， nxt_i=\min(\{j|j>i\land a_i=a_j\}\cup\{n+1\}) 。则可以确定对于所有 l\in [pre_i+1,i],r\in[i,nxt_i-1] 都有 a_i 在子区间 [l,r] 中出现恰好一次，因而 [l,r] 为独特子段。显然，这些独特子段的 l 和 r 对应的所有小正方形构成一个矩形。

（如序列 [3,1,2,1,3,2,1] ，对于 i=4,a_i=1,pre_i=2,nxt_i=7 ，其贡献的独特子段所对应的矩形即为下图，表示 [3,4],[3,5],[3,6],[4,4],[4,5],[4,6] 均为独特子段。）

显然，将每个 i 贡献的矩形覆盖至坐标系中，此时所有被覆盖过的小正方形所对应的区间一定是独特子段，而从未被覆盖过的一定不是（不存在 a_i 在这个子段中出现恰好一次）。

考虑扫描线求面积并的过程，设在 r 从小到大增加的过程中处理到第 i 行，由于无后效性，令 r\le i-1 的区域（即 r<i 的所有区间对应的小正方形）都已处理，若发现第 i 行（即坐标系中 i-1\le r\le i 的部分）存在未被覆盖的小正方形，即此时该行的面积并小于 i ，则出现区间右端点为 i 的非独特子段。

然后贪心处理，把 a_i 任意修改为未在序列中出现的数，此时，对于所有 l\in [1,i],r\in[i,n] 的区间 [l,r] 都会变为独特子段，这相当于在坐标系中覆盖了一个顶点为 (0,i-1),(i,i-1),(0,n),(0,n-1) 的矩形，那么只需要将扫描线中 [0,i] 的区间覆盖次数加一即可。

::::success[关于贪心的正确性] 对于一个未被覆盖的小正方形或其对应的非独特子段区间 [l,r] ，可以被多个 a_j(l\le j\le r) 的修改处理。但是，由于 r<i 的所有区间都已处理，对于任意 j<r ，修改 a_j 一定不会比修改 a_r 更优。

下图为序列 [3,1,2,1,3,2,1] 的情况，蓝、绿、黄色矩形分别带表 a_i=1,2,3 时的贡献。图中修改 a_6 或任意 a_j(j<6) 均可覆盖区间 [1,6],[1,7] 对应的小正方形，使区间 [1,6],[1,7] 变为独特子段。然而对于 r\ge 6 的部分，修改 a_6 的所覆盖的矩形（图中长虚线框住的部分）严格包含 a_j 所覆盖的矩形（图中短虚线为修改 a_2 所覆盖的矩形，在 r\ge 6 时被长虚线完全覆盖）,故而修改 a_6 一定不劣。

不过图中还可以看出来本题有一些特殊性质，虽然不知道有什么用 ::::

代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN=3e5+10;
int T,n,ans,a[MAXN],last[MAXN],l[MAXN];
int cov[MAXN*4],sum[MAXN*4];//cov: 线段树维护的区间被完整覆盖的次数 sum: 被覆盖过的长度和
void upd(int L,int R,int k,int i,int l,int r){
    int mid=(l+r)>>1;
    if(l==L&&R==r) cov[i]+=k;
    else{
        if(L<=mid) upd(L,min(R,mid),k,i*2,l,mid);
        if(R>mid) upd(max(L,mid+1),R,k,i*2+1,mid+1,r);
    }
    if(cov[i]>0) sum[i]=r-l+1;
    else if(l<r) sum[i]=sum[i*2]+sum[i*2+1];
    else sum[i]=0;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>T;
    while(T--){
        cin>>n;
        ans=0,memset(last,0,sizeof(last[0])*(n+5)),memset(l,0,sizeof(l[0])*(n+5));
        memset(cov,0,sizeof(cov[0])*(n+5)*4),memset(sum,0,sizeof(sum[0])*(n+5)*4);
        for(int i=1;i<=n;i++){
            cin>>a[i];
            l[i]=last[a[i]]+1;
            upd(l[i],i,1,1,1,n); //无需排序的在线扫描线（ 
            if(last[a[i]]) upd(l[last[a[i]]],last[a[i]],-1,1,1,n);
            if(sum[1]<i) ans++,upd(1,i,1,1,1,n); //发现右端点为i的非独特子段。
            last[a[i]]=i; //维护a[i]上一次的出现位置
        }
        cout<<ans<<"\n";
    }
    return 0;
}