题解 [ABC381E] 11/22 Subsequence

· · 题解

赛时竟然把好多暴力做法放过了，不能理解出题人的数据强度。

但是这里讲的是正确解法，不是暴力。

题意

当一个字符串 T 满足以下所有条件时，它就是好的字符串：

给定长度为 N 由1、2和/组成字符串 S，有 Q 次询问 L 和 R。假设 T = S[L:R]。求 T 的好的子序列（不一定连续）的最大长度。如果不存在这样的则输出 0。

分析

以任意一个 / 作为中心点，分别不断向左边和右边扩展 1 和 2，最长的子串取决于 1 和 2 数量的最小值。

这个问题貌似并不是很好用数据结构维护，想到二分答案。

设当前二分的长度为 x，判定即找到 L 的右边（包含 L）的第 x 个 1 和 R 的左边（包含 R）的第 x 个 2，判断这两个位置中间是否有 /。

判断一个区间是否有 / 可以使用前缀和，于是现在的问题变成了如何能快速的找到第 x 个，直接暴力跳肯定是不行的，可以使用倍增预处理。

接着就可以发现这个二分是不必要的，直接倍增求答案即可。

时间复杂度 O(n \log n + Q \log n)，空间复杂度 O(n \log n)。

代码

//the code is from chenjh
#include<cstdio>
#define MAXN 100005
using namespace std;
int n,q;
char s[MAXN];
int a[MAXN],nx[MAXN][18],pr[MAXN][18];//'/' 字符的前缀和，下一个 2，上一个 1。
int main(){
    scanf("%d%d %s",&n,&q,s+1);
    for(int i=1;i<=n;i++) a[i]=a[i-1]+(s[i]=='/');
    for(int i=1;i<=n+1;i++) pr[i][0]=i&&s[i-1]=='2'?i-1:pr[i-1][0];
    nx[n+1][0]=n+1;//注意边界情况。
    for(int i=n;i>=0;--i) nx[i][0]=i<n&&s[i+1]=='1'?i+1:nx[i+1][0];
    for(int k=1;k<18;k++)
        for(int i=0;i<=n+1;i++) pr[i][k]=pr[pr[i][k-1]][k-1],nx[i][k]=nx[nx[i][k-1]][k-1];//倍增预处理。
    for(int l,r;q--;){
        scanf("%d%d",&l,&r);
        bool fl=a[r]-a[l-1];//判断这段区间是否有 /，如果没有答案一定为 0。
        int ans=0;
        --l,++r;//因为包含，所以向两边多跳一个。
        for(int k=17,x,y;k>=0;--k){
            x=nx[l][k],y=pr[r][k];
            if(x<y&&a[y]-a[x-1]>0) ans|=1<<k,l=x,r=y;
        }
        printf("%d\n",ans?ans<<1|1:(int)fl);
    }
    return 0;
}