1684F - Diverse Segments - CodeForces Solution

#include<iostream>
#include <map>
#include <vector>
using namespace std;
int t,n,m;
map<int,vector<int>> h;
int main(){
	cin>>t;
	while(t--){
	cin>>n>>m;
	vector<int> a(n+1),l(n+1,n+1),mxl(n+1,n+1);
	int x,y,ans=n,st=n+1,en=0,minL=n+1;
	h.clear();
	for(int i=1;i<=n;i++){
		cin>>a[i];
		h[a[i]].push_back(i);
	}
	for(int i=0;i<m;i++){
		cin>>x>>y;
		l[y]=min(l[y],x);
	}
	for(int i=n;i>0;i--){
		minL=min(minL, l[i]);
		vector<int> *tmp=&h[a[i]];
		tmp->pop_back();
		int len=tmp->size();
		if (minL<i){
			int la=len?tmp->at(len-1):-1;
			if (minL<=la){
				en=max(la, en);
				vector<int>::iterator it=lower_bound(tmp->begin(),tmp->end(),minL);
				mxl[i-1]=*it;
				++it;
				st=min(st,(*it?*it:i));
			}
		}
	}
	for(int i=n;i>=en;i--){
		st=min(st, mxl[i]);
		ans=min(ans,max(0,i-st+1));
	}
	cout<<ans<<endl;	}
}