题解：CF1969E Unique Array

Description

定义一个子段是独特子段，当且仅当存在一个整数在这个子段中出现恰好一次。

给定序列

a

，求至少替换多少个元素，才能使得

a

的所有子段为独特子段。

Solution

考虑扫描线，定义一个二维平面，横轴代表左端点，纵轴代表右端点，点

(l,r)

代表子段

[l,r]

。

依次考虑每一个点，设

pre_i

为

a_i

前面第一个与其相同的数，

suf_i

为

a_i

后面第一个与其相同的数。

则对于所有

l \in [pre_i+1,i]

，

r \in [i,suf_i-1]

，

[l,r]

为独特子段，这在二维平面上可以转化为一个矩形，可以用扫描线维护矩形面积并，这样未被矩形覆盖的点就不是独特子段。

我们从右到左扫描线，设当前扫描到左端点

x

，若有对应右端点未被覆盖。此时有结论，直接将

a_x

替换为序列中未出现过的数一定是最优的。

感性证明一下，将

a_x

替换后，对于所有

l \in [1,x]

，

r \in [x,n]

，

[l,r]

都为独特子段。

由于是从右到左的扫描线，当扫描到

x

时，所有左端点

> x

的子段都被处理完成了，因此我们只关心修改后左端点

\le x

的子段，即扫描线左侧的影响。而修改

x

所影响的矩形可以完全覆盖修改其他点的矩形，从而得证。

Code

CPP

#include <bits/stdc++.h>
#define ls k<<1
#define rs k<<1|1
using namespace std;
const int N=3e5+5;
struct node{
	int l,r,k;
};
int T,n,a[N],b[N],pr[N],sf[N],ans;
int mi[N<<2],tag[N<<2];
vector<node>e[N];
int read(){
	int k=0;
	char ch=getchar();
	while(ch<'0'||ch>'9')
		ch=getchar();
	while(ch>='0'&&ch<='9')
		k=k*10+ch-'0',ch=getchar();
	return k;
}
void pushup(int k){
	mi[k]=min(mi[ls],mi[rs]);
}
void pushdown(int k){
	if(tag[k]){
		mi[ls]+=tag[k],tag[ls]+=tag[k];
		mi[rs]+=tag[k],tag[rs]+=tag[k];
		tag[k]=0;
	}
}
void build(int k,int l,int r){
	tag[k]=0;
	if(l==r){
		mi[k]=0;
		return;
	}
	int mid=(l+r)>>1;
	build(ls,l,mid),build(rs,mid+1,r);
	pushup(k);
}
void modify(int k,int l,int r,int x,int y,int v){
	if(x>y) return;
	if(x<=l&&r<=y){
		mi[k]+=v,tag[k]+=v;
		return;
	}
	pushdown(k);
	int mid=(l+r)>>1;
	if(x<=mid) modify(ls,l,mid,x,y,v);
	if(mid+1<=y) modify(rs,mid+1,r,x,y,v);
	pushup(k);
}
int main(){
	T=read();
	while(T--){
		ans=0;
		n=read();
		for(int i=1;i<=n;i++)
			a[i]=read();
		for(int i=1;i<=n;i++){
			pr[i]=b[a[i]];
			b[a[i]]=i;
		}
		for(int i=1;i<=n;i++) b[i]=n+1;
		for(int i=n;i>=1;i--){
			sf[i]=b[a[i]];
			b[a[i]]=i;
		}
		for(int i=1;i<=n;i++) b[i]=0;
		for(int i=1;i<=n;i++){
			e[pr[i]].push_back((node){i,sf[i]-1,-1});
			e[i].push_back((node){i,sf[i]-1,1});
		}
		build(1,1,n);
		for(int i=n;i>=1;i--){
			for(node j:e[i])
				modify(1,1,n,j.l,j.r,j.k);
			modify(1,1,n,1,i-1,1);
			if(mi[1]==0){
				modify(1,1,n,i,n,1);
				ans++;
			}
			modify(1,1,n,1,i-1,-1);
		}
		printf("%d\n",ans);
		for(int i=0;i<=n;i++)
			e[i].clear();
	}
	return 0;
}

题解：CF1969E Unique Array

文章操作

Description

Solution

Code

相关推荐

评论

题解：CF1969E Unique Array