Codeforces #792 : F. Diverse Segments

こっちもそこまで苦戦はしてないな。
https://codeforces.com/contest/1684/problem/F

問題

N要素の整数列Aと、M個の区間が与えられる。
Aのうちある区間内の要素を任意の値にできるとき、各区間内の全要素がdistinctであるようにしたい。
値を変更する区間は最短何要素か。

解法

Aの各要素について、「この要素を変更しない場合、この区間を変更しなければ条件に反する」という区間が求められる。
Aのうち変更しないprefixを総当たりし、上記区間の和集合の長さを取っていけばよい。

int T;
int N,M;
int A[201010];
int R[201010];
int TR[201010];
set<int> S[201010];

vector<int> cand[201010];
int ev[201010];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>M;
		vector<int> As;
		FOR(i,N) {
			cin>>A[i];
			As.push_back(A[i]);
			R[i]=i;
			TR[i]=-1;
			S[i].clear();
			cand[i].clear();
			ev[i]=-1;
		}
		sort(ALL(As));
		FOR(i,N) {
			A[i]=lower_bound(ALL(As),A[i])-As.begin();
			S[A[i]].insert(i);
		}
		FOR(i,M) {
			cin>>x>>y;
			R[x-1]=max(R[x-1],y-1);
		}
		multiset<int> need;
		multiset<int> fail;
		FOR(i,N) {
			if(i) R[i]=max(R[i],R[i-1]);
			auto it=S[A[i]].lower_bound(R[i]+1);
			it--;
			if(*it==i) continue;
			auto it2=S[A[i]].find(i);
			need.insert(*prev(it));
			ev[i]=*it;
			fail.insert(*next(it2));
			
		}
		
		int ret=N;
		FOR(i,N) {
			if(need.empty()) {
				ret=0;
			}
			else {
				ret=min(ret,*need.rbegin()+1-i);
				if(ev[i]>=0) need.insert(ev[i]);
			}
			if(fail.count(i)) break;
		}
		cout<<ret<<endl;
		
			
		
	}
}

まとめ

Div1Dよりはだいぶ簡単な気がする。