CF1223D

不需要动的一定值域连续

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<queue>

#define LL long long

using namespace std;

const int M = 310001;

int n,m,k,a[M],T,L[M],R[M],l,res,s;

int main()

{

	scanf("%d",&T);

	for(;T;T--)

	{

		scanf("%d",&n); m=0; res=0x3f3f3f3f; s=0;

		for(int i=1;i<=n;i++) L[i]=0x3f3f3f3f, R[i]=0;

		for(int i=1;i<=n;i++)

		{

			scanf("%d",&a[i]);

			if(!R[a[i]]) m++;

			L[a[i]]=min(L[a[i]],i);

			R[a[i]]=max(R[a[i]],i);

		}

		int r=0, x=0, y=1;

		for(int x=1;x<=n;x++) if(R[x])

		{

			if(s) s--;

			if(!s) r=R[x], s++;

			y=max(y,x);

			while((!R[y+1] || L[y+1]>r) &&y<n)

			{

				y++;

				if(!R[y]) continue;

				r=R[y]; s++;

			}

			res=min(res,m-s);

		}

		printf("%d\n",res);

	}

}

巴特西

CF1223D

CF1223D

最新文章

热门文章