UOJ小清新题表
题目摘要
给出一个排列 \(A\) 以及它的一个非空子序列 \(B\),给出一个 \(x\) 并进行若干次操作,每一次操作需要在 \(A\) 中选择一个长度恰好为 \(x\) 的区间并删除它的最小值。如果在操作结束以后剩下的数组恰好是 \(B\),那么就可以得到 \(x\) 分,否则得到 \(0\) 分。
有 \(q\) 组询问,所有的 \(A\) 序列都是一样的,但 \(B\) 序列不同。求每次询问能得到的最大得分。
\(B\) 序列是一个 01
串,若该位置上为 \(1\) ,则表示 \(A\) 序列中该位置的数在 \(B\) 序列中出现了。
数据范围
\(2≤n≤1000000\),\(1≤q≤10\),\(A\) 为一个排列,\(B\) 为 \(A\) 的非空子序列,且 \(B≠A\)。
思路
可以先看看样例和解释。
我们可以枚举每一个可能要被删除的点。若其要被删除,向左扩展到第一个比他小的点 \(l\),向右扩展到地一个比他小的 \(r\),那么这两个点构成的开区间 \((l,r)\) 就是这个点要被删除时的极大区间。由于要保证必须满足条件,所以要在所有的极大区间中取最小,即为所要求的 \(x\)。
维护区间大小或者联通性之类的这种东西,很容易可以想到并查集。可以对下标开两个并查集,分别向左向右扩展。
比如要找到左边第一个比当前点小的点,需要把数从大到小加入,用并查集维护不用删除的点,也就是 \(B\) 序列中的每个 \(1\), 如果遇到 \(1\) ,则 \(fa[i]=i\) ,否则 \(fa[i]=\text{Find}(\ i-1\ )\) 。显然最后查询的时候需要跳过 \(1\) 。向右扩展同理。这样你每次都能找到极大区间,只需要取个 \(\min\) 即可。
一开始用前缀和维护一下 \(1\) 的个数,此点对应的极大区间就是扩展后的区间中 \(1\) 的个数加上自己(\(+1\))。
代码
建议改成:三目运算符带师
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
const int INF=0x3f3f3f3f;
int n,ans;
int a[maxn],pos[maxn],L[maxn],R[maxn],sum[maxn];
char s[maxn];
inline int read(){
int x=0,fopt=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar())if(ch=='-')fopt=-1;
for(;isdigit(ch);ch=getchar())x=(x<<3)+(x<<1)+ch-48;
return x*fopt;
}
int Find(int x,int fa[]){
return x==fa[x]?x:(fa[x]=Find(fa[x],fa));
}
inline void Solve(){
for(int i=1;i<=n;i++)
sum[i]=(s[i]=='1')?sum[i-1]+1:sum[i-1];
ans=INF;R[n+1]=n+1;
for(int i=1;i<=n;i++)
L[i]=(s[i]=='1')?i:Find(i-1,L);
for(int i=n;i>=1;i--)
R[i]=(s[i]=='1')?i:Find(i+1,R);
for(int i=n;i>=1;i--){
int v=pos[i];
if(s[v]=='1'){
L[v]=Find(v-1,L);
R[v]=Find(v+1,R);
}else ans=min(ans,sum[Find(v,R)-1]-sum[Find(v,L)]+1);//注意是开区间
}
}
int main(){
n=read();
for(int i=1;i<=n;i++){
a[i]=read();
pos[a[i]]=i;
}
int Q=read();
while(Q--){
scanf("%s",s+1);
Solve();
printf("%d\n",ans);
}
return 0;
}