第一次打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)的