CF1896D

CF1896D

提供一种 ~~巨麻烦~~ 的 bitset 做法。

对于一个串，我们写一个前缀和，用树状数组动态维护，则位置 \(1\leq i < j \leq n\) 对应子串的和可以表示成 \(s_j-s_{i-1}\) ，原题就是求 \(s_j-s_{i-1}=s\) 是否可以满足。

受 这道题 的启发，这道题里我们可以用 bitset 维护这个前缀和数组，对于一个 bitset<N> f ，通过位运算判断 f&(f>>s) ，若结果不为零，则说明存在这样的子串。

对于修改，我们发现，每次修改对于 bitset 中 \(s_j-1\) 位置之前的位无影响，对于 \(s_j\) 之后的位置，右移或左移一位即可。

我们构造两个 bitset 串，一个串满足前 \(s_j-1\) 位都为 \(1\) ，另一个串为前一个串按位取反。将原串与这两个串分别与一下，后一个串左/右移一位，再或在一起，就完成了修改。

现在的问题在于，如何快速构造这样的两个串。

暴力不行，我们就用空间换时间。我们采取分块的思想，设块长为 \(k\) ，构造 \(\frac N k\) 个串，每个串依次增加 \(k\) 个 \(1\)。每次根据 \(s_j\) 暴力修改离他最“近”的串，就可以在 \(O(k)\) 的时间内构造出我们要的串。

协调一下时间空间，取 \(k=N^{\frac 13}\) ，再稍稍卡常就可以通过本题了。

#pragma GCC optimize(2)
#include<iostream>
#include<bitset>
#include<cmath>
using namespace std;
const int N=2e5+10,K=4e3;
int T,n,q,len;
bitset<N> s[K];
bitset<N> f,tmp,ttmp,g,h;
int k[N],a[N],t[N];
int read1() {
    int x=0;
    char ch=getchar();
    while(ch>'9' || ch<'0') ch=getchar();
    while(ch<='9' && ch>='0') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    return x;
}
void write1(int x) {
    if(x>9) write1(x/10);
    putchar(x%10+'0');
}
int lowbit(int x){
    return x&(-x);
}
void change(int x,int d){
    while(x<=n) t[x]+=d,x+=lowbit(x);
}

int sum(int x){
    int ans=0;
    while(x>0) ans+=t[x],x-=lowbit(x);
    return ans;
}
void init() {
    s[0].set(0);
    len=pow(N,0.33);
    for(int i=1; i<N; ++i) k[i]=(i-1)/len+1;
    for(int i=1; i<=k[N-1]; ++i) {
        s[i]=s[i-1];
        for(int j=(i-1)*len+1; j<=min(i*len,N-1); ++j) s[i].set(j);
    }

}
void solve() {
    n=read1(),q=read1();
    f=s[0];
    int ssum=0;
    for(int i=1;i<=n+n;++i) t[i]=0;
    for(int i=1; i<=n; ++i) {
        a[i]=read1();
        ssum+=a[i];
        f.set(ssum);
        change(i,a[i]);
    }
    for(int i=1,op,j,v; i<=q; ++i) {
        op=read1();
        if(op==1) {
            j=read1();
            if((f&(f>>j)).any()) putchar('Y'),putchar('E'),putchar('S'),putchar('\n');
            else putchar('N'),putchar('O'),putchar('\n');
        } else {
            j=read1(),v=read1();
            if(v==a[j]) continue;
            int sumj=sum(j);
            int tmpk=k[sumj-1];
            tmp=s[tmpk];
            for(int t=min(N-1,tmpk*len); t>=sumj; --t) tmp.reset(t);
            ttmp=tmp;
            ttmp.flip();
            g=tmp&f,h=ttmp&f;
            if(v-a[j]==1) f=(g)|(h<<1);
            else f=(g)|(h>>1);
            change(j,v-a[j]);
            a[j]=v;
        }
    }
}
int main() {
    T=read1();
    init();
    while(T--) solve();

    return 0;
}