UR #13 Yist

第一次打UR，打了一个半小时就弃疗了QAQ

这是我唯一一道考试的时候做出来的题目，其他两道连暴力都懒得写了

很容易发现对于每个要删除的点

我们找到左边第一个比他小的不用删除的点，右边第一个比他小的不用删除的点

中间这段区间就是对于这个点被删除时的极大区间

对于所有的区间我们取min就可以了

对于找到某个点左边第一个比他小的不用删除的点

我是这样考虑的：将数从大到小的进行添加，并用并查集维护不用删除的点

那么之后这个点存在的极大区间显然是这段区间里的1的个数+1

这个算法是O(na)的

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstdlib>

#include<cstring>

using namespace std;

const int maxn=1000010;

int n,T,ans;

int a[maxn],pos[maxn];

char b[maxn];

int L[maxn],R[maxn];

int sum[maxn];

int ufsL(int x){return L[x]==x?x:L[x]=ufsL(L[x]);}

int ufsR(int x){return R[x]==x?x:R[x]=ufsR(R[x]);}

void read(int &num){

	num=0;char ch=getchar();

	while(ch<'!')ch=getchar();

	while(ch>='0'&&ch<='9')num=num*10+ch-'0',ch=getchar();

}

void Solve(){

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

		if(b[i]=='1')sum[i]=sum[i-1]+1;

		else sum[i]=sum[i-1];

	}

	ans=n;L[0]=0;

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

		if(b[i]=='1')L[i]=i;

		else L[i]=ufsL(i-1);

	}R[n+1]=n+1;

	for(int i=n;i>=1;--i){

		if(b[i]=='1')R[i]=i;

		else R[i]=ufsR(i+1);

	}

	for(int i=n;i>=1;--i){

		int p=pos[i];

		if(b[p]=='1'){

			L[p]=ufsL(p-1);

			R[p]=ufsR(p+1);

		}else{

			int A=ufsL(p);

			int B=ufsR(p);

			ans=min(ans,sum[B-1]-sum[A]+1);

		}

	}return;

}

int main(){

	read(n);

	for(int i=1;i<=n;++i)read(a[i]),pos[a[i]]=i;

	scanf("%d",&T);

	while(T--){

		scanf("%s",b+1);

		Solve();

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

	}return 0;

}

题解给出了一种O(n)的做法，还是回顾刚才的思路

我们注意到我们的并查集只有删除操作

也就是说如果一个点扩展的时候访问到之前已经扩展过的点

这个点的区间长度一定比之前扩展的那个点的区间长度要长

由于我们取的是min，所以我们就不用扩展了

这样我们就可以保证每个元素只访问一次，每次暴力扩展即可

时间复杂度显然是O(n)的

巴特西

UR #13 Yist

最新文章

热门文章