Codeforces ECR #165 : E. Unique Array

これは割とすんなり。
https://codeforces.com/contest/1969/problem/E

問題

整数列Aが与えられる。
Aのうち長さ2以上の連続部分列を選ぶと、必ず1回しか登場しない値があるようにしたい。
最小何要素Aを書き換えれば、そうなるか。

解法

連続部分列の右端Rを走査していき、条件を満たさないケースがありそうならその右端の値を新しい値に書き換えて行く。
SegTreeを使い、A[0...R]のうちある値xが登場する添え字の末尾2つがX,Yとすると、連続部分列の左端が[X+1,Y]であれば、xによって条件を満たすことになる。
区間加算・区間最小値を求めるSegTreeにより、各xについて全区間をカバーできるか判定していけばよい。

int T,N,A[303030];

int PP[606060];
int P[606060];

template<class V,int NV> class SegTree_3 {
public:
	vector<V> val, ma;
	SegTree_3(){
		int i;
		val.resize(NV*2,0); ma.resize(NV*2,0);
	};
	
	V getval(int x,int y,int l=0,int r=NV,int k=1) {
		if(r<=x || y<=l || y<=x) return 1<<20;
		if(x<=l && r<=y) return ma[k];
		return val[k]+min(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	
	void update(int x,int y, V v,int l=0,int r=NV,int k=1) {
		if(l>=r||y<=x) return;
		if(x<=l && r<=y) {
			val[k]+=v;
			ma[k]+=v;
		}
		else if(l < y && x < r) {
			update(x,y,v,l,(l+r)/2,k*2);
			update(x,y,v,(l+r)/2,r,k*2+1);
			ma[k]=val[k]+min(ma[k*2],ma[k*2+1]);
		}
	}
};
SegTree_3<int,1<<20> st;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		FOR(i,2*N+3) {
			PP[i]=P[i]=0;
			x=st.getval(i,i+1);
			st.update(i,i+1,-x);
		}
		
		
		int ret=0;
		for(i=1;i<=N;i++) {
			cin>>x;
			A[i]=x;
			if(P[x]>0) {
				st.update(PP[x]+1,P[x]+1,-1);
				st.update(P[x]+1,i+1,1);
				
				y=st.getval(1,i+1);
				st.update(PP[x]+1,P[x]+1,1);
				st.update(P[x]+1,i+1,-1);
				if(y==0) {
					A[i]=N+(++ret);
				}
			}
			x=A[i];
			st.update(PP[x]+1,P[x]+1,-1);
			st.update(P[x]+1,i+1,1);
			PP[x]=P[x];
			P[x]=i;
			
			
		}
		cout<<ret<<endl;
	}
}

まとめ

こういう問題、なんかCodeforcesに多いイメージ。