【洛谷P5640】【CSGRound2】逐梦者的初心 | Mrsrz's blog

bitset

题目大意：

给定字符串 $a$ 和一个初始为空的字符串 $t$。每次会在 $t$ 的前面或者后面插入一个字符，然后询问有多少个 $t$ 的后缀 $t’$，满足，和 $a$ 的长度为 $|t’|$ 的前缀逐位匹配，没有一位是相同的。

题解：

一道bitset题。

在前面加字符，相当于多了个串。在后面加字符，相当于之前每个后缀要多匹配一位。

观察数据范围，考虑用bitset优化

我们在前面加字符，只需要看原来的串整体右移一位后是否有字符匹配，再看看新加入的字符能否和第一位匹配即可。

令 $b_i$ 表示当前字符串 $t$ 整体往右移 $i$ 位后能否产生贡献。在前面加字符时，先整体向左移一格（因为加入字符相当于整体已经向右移动了），再and上新加入的字符没出现过的位置（这个字符出现的位置不能匹配）。

考虑在后面加入字符，需要一次考虑新加入的字符和 $s_1,s_2,\dots,s_{|t|}$ 能否匹配。记录新加入的字符在 $s$ 中的出现位置即可。

我们另外记录 $p_i$ 表示长度为 $i$ 的后缀能否产生贡献。在后面加字符时，先左移一格表示每个后缀都变长了，将 $p$ 整体and上新加入字符不能匹配的位置即可。在前面加字符时，直接对 $p_{|t|}$ 赋值为 $1$ 即可。对 $b$ 数组这里也要修改，可以通过简单的左移、取反、取交集操作实现。

统计答案时直接输出p.count()即可。

时间复杂度 $O(\frac{m^2}\omega)$。

Code：

#include<cstdio>
#include<cctype>
#include<bitset>
using namespace std;
const int N=33335;
typedef bitset<N>BitSet;
BitSet B[1005],iB[1005],s,ok;
int n,m,a[N];
inline int readint(){
    int c=getchar(),d=0;
    for(;!isdigit(c);c=getchar());
    for(;isdigit(c);c=getchar())d=d*10+(c^'0');return d;
}
int main(){
    n=readint(),m=readint();
    for(int i=0;i<m;++i)B[readint()].set(i);
    for(int i=m;i<n;++i)readint();
    ok.set();
    for(int i=1;i<=1000;++i)iB[i]=~B[i];
    for(int T=0;T<m;++T){
        int op=readint(),x=readint();
        if(op==1){
            ok=(ok>>1)&(iB[x]);
            s[T]=ok[0];
        }else{
            s<<=1;
            s.set(0);
            s&=iB[x];
            ok&=(~(B[x]>>T));
        }
        printf("%d\n",s.count());
    }
    return 0;
}