浅谈 bitset 在数据结构中的一些应用

· · 算法·理论

省流：不说 DAG 可达性。

1

题目

P3380 【模板】树套树

题面

查询 k 在区间内的排名，查询区间内排名为 k 的值，修改某一位置上的数值，查询 k 在区间内的前驱后继（n,q\le5\times10^4，a_i\le10^8，可离线，本处设 n,q 同阶，要求做到 O(n\sqrt n+\frac{n^2}{w})）。

::::info[做法]

以此道题作为整篇文章的板子题，还可以让大家看一看如何手写 bitset。

由于 bitset 的一些神秘性质，我们不妨将每个数离散化并且让每个数互不相同。

首先考虑查询：如果我们能取一个区间的位集合，那查询是可以直接 O(\frac{n}{w}) 做的。我们将整个序列分为 B 个块，记录 B 个 bitset，第 i 个 bitset 记录的是第 1 个到第 i 个块所有数的位集合。因为每个数互不相同，加入一个数就相当于在一个位置上异或一下。由于异或的性质，我们可以再求出每个块所有数的位集合后再前缀异或就可以做到预处理 O(\frac{nB}{w})。查询的话通过整块差分一下，散块加入进去每次为 O(\frac{n}{w}+\frac{n}{B})。但是你还有修改：有 B 个块，故每次只有 O(B) 个块会被修改，总复杂度为 O(\frac{nB}{w}+\frac{n^2}{w}+\frac{n^2}{B}+nB)。取 B=\sqrt n 可以做到 O(\frac{n\sqrt n}{w}) 空间，O(n\sqrt n+\frac{n^2}{w}) 的时间复杂度。

看起来好像比 O(n\log^2n) 的树套树要慢，实际上比树套树模板中树套树做法应该是所有做法中最慢的（算出来要比树套树慢 3 倍多，实际上要比大多数人的树套树快了不止 3 倍多，总时间连 1s 都没有）。

代码：

#include <bits/stdc++.h>
using namespace std;
//此处省略快读
constexpr int N=5e4;
constexpr int block=300;
struct bitst{
    unsigned long long a[1600];
    inline void reset(){__builtin_memset(a,0,sizeof(a));}
    inline bitst operator=(const bitst&b)noexcept{__builtin_memcpy(a,b.a,sizeof(a));return*this;}
    friend inline bitst operator^(bitst a,const bitst&b)noexcept{
        for(int i=0;i<1600;++i)a.a[i]^=b.a[i];
        return a;
    }
    friend inline bitst operator^=(bitst&a,const bitst&b)noexcept{
        for(int i=0;i<1600;++i)a.a[i]^=b.a[i];
        return a;
    }
    inline void reset(int x)noexcept{a[x>>6]&=~(1ull<<(x&63));}
    inline void set(int x)noexcept{a[x>>6]|=(1ull<<(x&63));}
    inline void flip(int x)noexcept{a[x>>6]^=(1ull<<(x&63));}
    inline bool operator[](int x)noexcept{return (a[x>>6]>>(x&63))&1;}
    inline bool have(int x)noexcept{return (a[x>>6]>>(x&63))&1;}
    inline int _Find_prev(int pos)noexcept{
        if(pos==0)return -1;--pos;
        unsigned long long tmp=a[pos>>6]<<(63-(pos&63));
        if(tmp)return((pos>>6)<<6)+(pos&63)-__builtin_clzll(tmp);
        for(int i=(pos>>6)-1;~i;--i)if(a[i])return __lg(a[i])+(i<<6);
        return -1;
    }
    inline int _Find_next(int pos)noexcept{
        ++pos;if(pos==(1600<<6))return 1600<<6;
        unsigned long long tmp=a[pos>>6]>>(pos&63);
        if(tmp)return __builtin_ctzll(tmp)+(pos&63)+((pos>>6)<<6);
        for(int i=(pos>>6)+1;i<1600;++i){
            if(a[i])return __builtin_ctzll(a[i])+(i<<6);
        }return 1600<<6;
    }
    inline int _Find_val(int pos)noexcept{
        for(int i=0;i<1600;++i){
            if((pos-=__builtin_popcountll(a[i]))<=0){
                i=((i+1)<<6)-1;
                while(1){
                    if(have(i)&&!pos)return i;
                    pos+=have(i--);
                }
            }
        }return 1600<<6;
    }
    inline int _Find_rank(int k)noexcept{
        int pos=0;
        for(int i=(k>>6)-1;~i;--i){
            pos+=__builtin_popcountll(a[i]);
        }
        for(int i=(k>>6)<<6;i<k;++i)pos+=have(i);
        return pos+1;
    }
};
bitst t[(N+5)/block+2],s1;
int pa[(N+5)<<1],sa[(N+5)<<1];
struct node{int x,id;}st[(N+5)<<1];int top;
struct node2{
    int op,l,r,k;
}q[N+5];
int n,m,a[N+5],bl[N+5],L[(N+5)/block+2],R[(N+5)/block+2],blcnt;
inline void query(int l,int r){
    if(bl[l]+1>=bl[r]){
        s1.reset();
        for(int i=l;i<=r;++i)s1.flip(a[i]);
        return;
    }
    s1=t[bl[r]-1]^t[bl[l]];
    for(int i=R[bl[l]];i>=l;--i)s1.flip(a[i]);
    for(int i=L[bl[r]];i<=r;++i)s1.flip(a[i]);

}
inline void solve_rank(int l,int r,int k){query(l,r);cout<<   s1._Find_rank(k)   <<'\n';}
inline void solve_val (int l,int r,int k){query(l,r);cout<<st[s1._Find_val (k)].x<<'\n';}
inline void solve_prev(int l,int r,int k){query(l,r);cout<<(((top=s1._Find_prev(k))==(-1     ))?-2147483647:st[top].x)<<'\n';}
inline void solve_next(int l,int r,int k){query(l,r);cout<<(((top=s1._Find_next(k))==(1600<<6))? 2147483647:st[top].x)<<'\n';}
inline void change(int p,int x){for(int i=bl[p];i<=blcnt;++i)t[i].flip(a[p]),t[i].flip(x);a[p]=x;}
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;++i)cin>>a[i],st[++top]=node{a[i],i};
    for(int i=1;i<=m;++i){
        cin>>q[i].op;
        switch(q[i].op){
            case 1:cin>>q[i].l>>q[i].r>>q[i].k,st[++top]=node{q[i].k,i+n};break;
            case 2:cin>>q[i].l>>q[i].r>>q[i].k                           ;break;
            case 3:cin>>q[i].l        >>q[i].k,st[++top]=node{q[i].k,i+n};break;
            case 4:cin>>q[i].l>>q[i].r>>q[i].k,st[++top]=node{q[i].k,i+n};break;
            case 5:cin>>q[i].l>>q[i].r>>q[i].k,st[++top]=node{q[i].k,i+n};break;
        }
    }
    sort(st+1,st+top+1,[](node&x,node&y){return x.x<y.x;});
    for(int i=1,now=1;i<=top;++i){if(st[now].x!=st[i].x)now=i;pa[i]=now;}
    for(int i=top,now=top;i>=1;--i){if(st[now].x!=st[i].x)now=i;sa[i]=now;}
    for(int i=1;i<=top;++i){
        if(st[i].id<=n){a[st[i].id]=i;continue;}
        st[i].id-=n;
        switch(q[st[i].id].op){
            case 1:q[st[i].id].k=pa[i];break;
            case 3:q[st[i].id].k=i;break;
            case 4:q[st[i].id].k=pa[i];break;
            case 5:q[st[i].id].k=sa[i];break;
        }
    }
    for(int i=1;i<=block;++i)bl[i]=1;for(int i=block+1;i<=n;++i)bl[i]=bl[i-block]+1;
    blcnt=bl[n];for(int x=1;x<=bl[n];++x){
        L[x]=(x-1)*block+1,R[x]=min(x*block,n);t[x]=t[x-1];
        for(int i=L[x];i<=R[x];++i)t[x].flip(a[i]);
    }
    for(int i=1;i<=m;++i){
        switch(q[i].op){
            case 1:solve_rank(q[i].l,q[i].r,q[i].k);break;
            case 2:solve_val (q[i].l,q[i].r,q[i].k);break;
            case 3:change    (q[i].l,       q[i].k);break;
            case 4:solve_prev(q[i].l,q[i].r,q[i].k);break;
            case 5:solve_next(q[i].l,q[i].r,q[i].k);break;
        }
    }
    return 0;
}

::::

2

题目

P4175 [CTSC2008] 网络管理

题面

给你一棵树，单点修，链求第 k 大（n,q\le80000，a_i\le10^8，可离线，本处要求做到 O(n\sqrt n+\frac{n^2}{w})）。

::::info[做法]

跟第一个题一样，只不过从序列转到树上问题，改成树分块随机撒点即可。

代码：

constexpr int N=1e5+5;
constexpr int block=200;
bitst t[block+2],c[block+2],nowt,nowc,ans;int im[block+2],imid[N];
struct node{int x,id;}st[N<<1];int top,B;
struct node2{
    int op,l,r,k;
}q[N];
int n,m,a[N],f[N],stt[22][N],dfn[N],idn;
vector<int>e[N];
inline int get(int x,int y){return dfn[x]<dfn[y]?x:y;}
inline int lca(int u,int v){
    if(u==v)return u;if((u=dfn[u])>(v=dfn[v]))swap(u,v);
    int k=__lg(v-u++);return get(stt[k][u],stt[k][v-(1<<k)+1]);
}
inline void dfs(int u,int fa){nowt.set(a[u]),nowc.set(u);stt[0][dfn[u]=++idn]=f[u]=fa;
    if(imid[u])t[imid[u]]=nowt,c[imid[u]]=nowc;
    for(auto v:e[u])if(v!=fa)dfs(v,u);nowt.reset(a[u]),nowc.reset(u);
}
inline void solve1(int x,int y,int k){
    ans.reset();
    ans.flip(a[lca(x,y)]);
    while(x&&!imid[x])ans.flip(a[x]),x=f[x];
    while(y&&!imid[y])ans.flip(a[y]),y=f[y];
    if(x)ans^=t[imid[x]];
    if(y)ans^=t[imid[y]];
    int cal=ans._Find_val(k);
    if(cal==(2560<<6))cout<<"invalid request!\n";
    else cout<<st[cal].x<<'\n';
}
inline void solve2(int p,int x){for(int i=1;i<=B;++i)c[i][p]?(t[i].flip(x),t[i].flip(a[p])):void();a[p]=x;}
signed main(){
    cin>>n>>m;B=min(block,n);
    for(int i=1;i<=n;++i)cin>>a[i],st[++top]=node{a[i],i},f[i]=i;
    shuffle(f+1,f+n+1,mt19937(time(NULL)));for(int i=1;i<=B;++i)im[i]=f[i],imid[f[i]]=i;
    for(int i=1,u,v;i<n;++i)cin>>u>>v,e[u].emplace_back(v),e[v].emplace_back(u);
    for(int i=1;i<=m;++i){
        cin>>q[i].op>>q[i].l>>q[i].r;
        if(q[i].op)q[i].k=q[i].op,q[i].op=1;
        else q[i].op=2,st[++top]=node{q[i].r,i+n};
    }
    sort(st+1,st+top+1,[](node&x,node&y){return x.x>y.x;});
    for(int i=1;i<=top;++i)(st[i].id<=n)?(a[st[i].id]=i):(q[st[i].id-n].r=i);
    dfs(1,0);
    for(int i=1;(1<<i)<=n;++i){
        for(int j=1;j+(1<<i)-1<=n;++j){
            stt[i][j]=get(stt[i-1][j],stt[i-1][j+(1<<(i-1))]);
        }
    }
    for(int i=1;i<=m;++i)(q[i].op==1)?solve1(q[i].l,q[i].r,q[i].k):solve2(q[i].l,q[i].r);
    return 0;
}

::::

3

题目

P4688 [Ynoi Easy Round 2016] 掉进兔子洞

题面

一个长为 n 的序列 a，有 m 个询问，每次询问三个区间，把三个区间中同时出现的数一个一个删掉，问最后三个区间剩下的数的个数和，询问独立。注意这里删掉指的是一个一个删，不是把等于这个值的数直接删完（n,m\le10^5，a_i\le10^9，三秒，本处要求强制在线）。

::::info[做法]

我也不知道为什么整个题解区没有一个在线做法。

先说一下本题的离线做法：首先先把整个序列离散化一下使值域在 \left[1,10^5\right]。

答案就是 r_3-l_3+r_2-l_2+r_1-l_1+3-3k，其中 k 表示区间共有的数的个数。

我们的想法是让最终的 bitset 中的每个数都落到不同的位置上，则在 [pos,pos+cnt_i) 都用来统计 i 这个数。每次直接对三个 bitset 求并在来个 count 即可，很容易就拆成 3m 次询问上莫队。

考虑怎么转在线做法：例如你是从高往低放数，我们每次从整块转移：每次加数若你不知道一个数存了多少个 1，直接找到从你应该第一个放的数往前找第一个 0 放，并且记录一下放的位置。

但是往前找第一个 0 最劣复杂度不是 O(\frac{n}{w}) 的吗？慢着，我们仔细分析一下：每种数最多只会找 1 次。若你加了这个数，则说明这个数的对应的位置没有填满，每次找最多为 \frac{cnt_i}{w}+O(1) 次，假设块长为 B，总的复杂度最劣是 O(\sum_{i=1}^n\frac{cnt_i}{w}+B)=O(\frac{n}{w}+B) 的。

空间给得有点不够，我们把块长开小点。

代码：

//省略快读
#define pcnt(x) __builtin_popcountll(x)
struct bitst{
    unsigned long long a[1600];
    inline void reset(){__builtin_memset(a,0,sizeof(a));}
    inline bitst operator=(const bitst&b)noexcept{__builtin_memcpy(a,b.a,sizeof(a));return*this;}
    inline void reset(int x)noexcept{a[x>>6]&=~(1ull<<(x&63));}
    inline void set(int x)noexcept{a[x>>6]|=(1ull<<(x&63));}
    inline void flip(int x)noexcept{a[x>>6]^=(1ull<<(x&63));}
    inline bool operator[](int x)noexcept{return (a[x>>6]>>(x&63))&1;}
    inline bool have(int x)noexcept{return (a[x>>6]>>(x&63))&1;}
    inline int _Find_prev0(int pos)noexcept{
        unsigned long long tmp=(~a[pos>>6])<<(63-(pos&63));
        if(tmp)return((pos>>6)<<6)+(pos&63)-__builtin_clzll(tmp);
        for(int i=(pos>>6)-1;~i;--i)if(~a[i])return __lg(~a[i])+(i<<6);
        return -1;
    }
};
constexpr int N=1e5+50;
constexpr int block=500;
bitst bs[N/block+5][N/block+5],t,t1,t2,t3;
int n,m,a[N],b[N],cnt[N],fr[N],bl[N],L[N/block+5],R[N/block+5];
#define query(x,l,r)\
    if(bl[l]+1>=bl[r]){\
        t##x.reset();\
        for(int i=l;i<=r;++i){\
            t##x.set(fr[a[i]]--);\
        }\
        for(int i=l;i<=r;++i)fr[a[i]]=cnt[a[i]];\
    }else{\
        t##x=bs[bl[l]+1][bl[r]-1];\
        for(int i=R[bl[l]];i>=l;--i){\
            (fr[a[i]]!=cnt[a[i]])?(t##x.set(fr[a[i]]--)):(fr[a[i]]=t##x._Find_prev0(fr[a[i]]),t##x.set(fr[a[i]]--));\
        }\
        for(int i=L[bl[r]];i<=r;++i){\
            (fr[a[i]]!=cnt[a[i]])?(t##x.set(fr[a[i]]--)):(fr[a[i]]=t##x._Find_prev0(fr[a[i]]),t##x.set(fr[a[i]]--));\
        }\
        for(int i=R[bl[l]];i>=l;--i)fr[a[i]]=cnt[a[i]];\
        for(int i=L[bl[r]];i<=r;++i)fr[a[i]]=cnt[a[i]];\
    }
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;++i)cin>>a[i],b[i]=a[i];sort(b+1,b+n+1);int nb=unique(b+1,b+n+1)-b-1;
    for(int i=1;i<=n;++i)a[i]=lower_bound(b+1,b+nb+1,a[i])-b;
    for(int i=1;i<=n;++i)++cnt[a[i]];for(int i=1;i<=n;++i)cnt[i]+=cnt[i-1];
    fill(bl+1,bl+min(n,block)+1,1);for(int i=block+1;i<=n;++i)bl[i]=bl[i-block]+1;
    __builtin_memcpy(fr,cnt,sizeof(int)*(n+2));
    for(int i=1;i<=bl[n];++i)L[i]=(i-1)*block+1,R[i]=min(i*block,n);
    for(int i=1;i<=bl[n];++i){
        t.reset();
        for(int j=i;j<=bl[n];++j){
            for(int k=L[j];k<=R[j];++k)t.set(fr[a[k]]--);
            bs[i][j]=t;
        }
        __builtin_memcpy(fr,cnt,sizeof(int)*(n+2));
    }
    for(int p=1,l1,r1,l2,r2,l3,r3;p<=m;++p){
        cin>>l1>>r1>>l2>>r2>>l3>>r3;
        {query(1,l1,r1)};{query(2,l2,r2)};{query(3,l3,r3)};
        int ans=0;
        int ans0=0,ans1=0,ans2=0,ans3=0;
        int ans4=0,ans5=0,ans6=0,ans7=0;
        for(int i=0;i<1600;i+=8){
            ans0+=pcnt(t1.a[i]&t2.a[i]&t3.a[i]),
            ans1+=pcnt(t1.a[i^1]&t2.a[i^1]&t3.a[i^1]),
            ans2+=pcnt(t1.a[i^2]&t2.a[i^2]&t3.a[i^2]),
            ans3+=pcnt(t1.a[i^3]&t2.a[i^3]&t3.a[i^3]),
            ans4+=pcnt(t1.a[i^4]&t2.a[i^4]&t3.a[i^4]),
            ans5+=pcnt(t1.a[i^5]&t2.a[i^5]&t3.a[i^5]),
            ans6+=pcnt(t1.a[i^6]&t2.a[i^6]&t3.a[i^6]),
            ans7+=pcnt(t1.a[i^7]&t2.a[i^7]&t3.a[i^7]);
        }ans=ans0+ans1+ans2+ans3+ans4+ans5+ans6+ans7;
        cout<<r1-l1+1+r2-l2+1+r3-l3+1-3*ans<<'\n';
    }
    return 0;
}

::::

4

题目

P4135 作诗

题面

给定长度为 n 的序列，q 次查询有多少个数出现正偶数次，强制在线（正常 n,q\le10^5，本处要求空间做到 O(\frac{n\sqrt n\log n}{w})，时间做到 O(n\sqrt n+\frac{n^2}{w})）。

::::info[做法]

用总数量减去奇数次的数量就是偶数次的数量。奇数次的轻松用异或前缀维护。

区间出现的数的种数考虑 bitset 求并：但是显然它没有可差分性，我们不妨对于块间建立 ST 表，可以做到空间 O(\frac{n\sqrt n\log n}{w})。

代码：

//此处省略快读
constexpr int N=1e5+5;
constexpr int block=300;
bitset<N>t1[N/block+2],t2[11][N/block+2],s1,s2;
unordered_map<int,int>ma[N/block+2];
int n,m,a[N],bl[N],L[N/block+2],R[N/block+2],blcnt,lastans;
inline bitset<N>qu(int l,int r){
    int k=__lg(r-l+1);
    return t2[k][l]|t2[k][r-(1<<k)+1];
}
inline void query1(int l,int r){
    if(bl[l]+1>=bl[r]){
        s1.reset();
        for(int i=l;i<=r;++i)s1.flip(a[i]);
        return;
    }
    s1=t1[bl[r]-1]^t1[bl[l]];
    for(int i=R[bl[l]];i>=l;--i)s1.flip(a[i]);
    for(int i=L[bl[r]];i<=r;++i)s1.flip(a[i]);
}
inline void query2(int l,int r){
    if(bl[l]+1>=bl[r]){
        s2.reset();for(int i=l;i<=r;++i)s2.set(a[i]);
        return;
    }
    s2=qu(bl[l]+1,bl[r]-1);
    for(int i=R[bl[l]];i>=l;--i)s2.set(a[i]);
    for(int i=L[bl[r]];i<=r;++i)s2.set(a[i]);
}
inline void solve(int l,int r){
    query1(l,r),query2(l,r),lastans=(s1^s2).count();cout<<lastans<<'\n';
}
signed main(){
    cin>>n>>m;cin>>m;
    for(int i=1;i<=n;++i)cin>>a[i];
    for(int i=1;i<=block;++i)bl[i]=1;for(int i=block+1;i<=n;++i)bl[i]=bl[i-block]+1;
    blcnt=bl[n];for(int x=1;x<=bl[n];++x){
        L[x]=(x-1)*block+1,R[x]=min(x*block,n);
        t1[x]=t1[x-1];
        for(int i=L[x];i<=R[x];++i)
        t1[x].flip(a[i]),t2[0][x].set(a[i]),++ma[x][a[i]];
    }
    for(int i=1;(1<<i)<=blcnt;++i){
        for(int j=1;j+(1<<i)-1<=blcnt;++j){
            t2[i][j]=t2[i-1][j]|t2[i-1][j+(1<<(i-1))];
        }
    }
    for(int i=1,l,r;i<=m;++i){
        cin>>l>>r;
        l=(l+lastans)%n+1,r=(r+lastans)%n+1;
        if(l>r)swap(l,r);
        solve(l,r);
    }
    return 0;
}

::::

4

题目

P8930 「TERRA-OI R1」神，不惧死亡

题面

长度为 n 的序列 a，q 次操作，单点修或区间 \left[l,r\right] 内找到值在 \left[a,b\right] 范围内出现次数为偶数的最大数的后继（n,q\le10^5，本处要求强制在线，并且时间复杂度做到 O(n\sqrt n+\frac{n^2}{w})）。

::::info[做法]

跟上面那个题一样但是多了带修。

前缀异或的部分很好单点修，维护区间出现的数还带好像有点困难，但随便维护一个 O(B) 单点修的 ST 表就很轻松了。注意一下 ST 表单点修的细节处理。

代码：

//此处省略快读
constexpr int N=1e5+5;
constexpr int block=300;
bitset<N>t1[N/block+2],t2[11][N/block+2],s1,s2;
unordered_map<int,int>ma[N/block+2];
int n,m,a[N],bl[N],L[N/block+2],R[N/block+2],blcnt;
inline bitset<N>qu(int l,int r){
    int k=__lg(r-l+1);
    return t2[k][l]|t2[k][r-(1<<k)+1];
}
inline void solve1(int p,int x){
    for(int i=bl[p];i<=blcnt;++i)t1[i].flip(a[p]),t1[i].flip(a[p]+x);
    if(!(--ma[bl[p]][a[p]])){
        t2[0][bl[p]].reset(a[p]);
        for(int i=1;(1<<i)<=blcnt;++i){
            for(int j=max(1,bl[p]-(1<<i)+1);j+(1<<i)-1<=blcnt&&j<=bl[p];++j){
                (t2[i-1][j][a[p]]||t2[i-1][j+(1<<(i-1))][a[p]])?(1):(t2[i][j].reset(a[p]));
            }
        }
    }a[p]+=x;
    if(!(ma[bl[p]][a[p]]++)){
        t2[0][bl[p]].set(a[p]);
        for(int i=1;(1<<i)<=blcnt;++i){
            for(int j=max(1,bl[p]-(1<<i)+1);j+(1<<i)-1<=blcnt&&j<=bl[p];++j){
                (t2[i-1][j][a[p]]||t2[i-1][j+(1<<(i-1))][a[p]])?(t2[i][j].set(a[p])):(1);
            }
        }
    }
}
inline void query1(int l,int r){
    if(bl[l]+1>=bl[r]){
        s1.reset();
        for(int i=l;i<=r;++i)s1.flip(a[i]);
        return;
    }
    s1=t1[bl[r]-1]^t1[bl[l]];
    for(int i=R[bl[l]];i>=l;--i)s1.flip(a[i]);
    for(int i=L[bl[r]];i<=r;++i)s1.flip(a[i]);
}
inline void query2(int l,int r){
    if(bl[l]+1>=bl[r]){
        s2.reset();
        for(int i=l;i<=r;++i)s2.set(a[i]);
        return;
    }
    s2=qu(bl[l]+1,bl[r]-1);
    for(int i=R[bl[l]];i>=l;--i)s2.set(a[i]);
    for(int i=L[bl[r]];i<=r;++i)s2.set(a[i]);
}
inline void solve2(int l,int r,int p,int q){
    int ans=0;
    query1(l,r),query2(l,r);s1^=s2;
    s1[p]?(ans=p):(ans=s1._Find_next(p));
    if(ans>q){cout<<-1<<'\n';return;}
    ans=s2._Find_next(ans);
    if(ans>q)cout<<-1<<'\n';
    else cout<<ans<<'\n';
}
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;++i)cin>>a[i];
    for(int i=1;i<=block;++i)bl[i]=1;for(int i=block+1;i<=n;++i)bl[i]=bl[i-block]+1;
    blcnt=bl[n];for(int x=1;x<=bl[n];++x){
        L[x]=(x-1)*block+1,R[x]=min(x*block,n);
        t1[x]=t1[x-1];
        for(int i=L[x];i<=R[x];++i)
        t1[x].flip(a[i]),t2[0][x].set(a[i]),++ma[x][a[i]];
    }
    for(int i=1;(1<<i)<=blcnt;++i){
        for(int j=1;j+(1<<i)-1<=blcnt;++j){
            t2[i][j]=t2[i-1][j]|t2[i-1][j+(1<<(i-1))];
        }
    }
    int op,l,r,p,q,x;
    for(int i=1;i<=m;++i){
        cin>>op,op==1?(cin>>p>>x,solve1(p,x)):(cin>>l>>r>>p>>q,solve2(l,r,p,q));
    }
    return 0;
}

::::

5

题目

CF914F Substrings in a String

题面

给定一个字符串 s（均为小写字母），以及 q 个操作，每次单点修或取 s 在区间为 \left[l,r\right] 的字串求 y 作为子串在其中出现的次数（|s|\le 10^5，q\le10^5，询问的字符串 y 的总长度不超过 10^5）。

::::info[做法]

用 26 个 bitset 存每个字符出现的位置。对于每次询问的字符串 y，\cap_{i=0}^{|y|-1}bit_i>>i 所得第 i 位表示的是是否满足 s_i=y_0,s_{i+1}=y_1,...s_{i+|y|-1}=y_{|y|-1}，即 s 在 [i,i+|y|-1] 的子串是否与 y 相等。最终我们再在所求的 bitset 中相应位置算一下 1 的个数即可。

代码：

int n,m;char c;
string s,t;
bitset<100005>b[26],ans;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>s>>m;n=s.size();for(int i=0;i<n;++i)b[s[i]-'a'].set(i);
    for(int o=0,op,i,l,r;o<m;++o){
        cin>>op;
        switch(op){
            case 1:cin>>i>>c,--i,b[s[i]-'a'].reset(i),s[i]=c,b[s[i]-'a'].set(i);break;
            case 2:cin>>l>>r>>t,--l,--r;if((r-l+1)<(int)t.size()){cout<<0<<'\n';break;}
            for(i=0,ans.set();i<(int)t.size();++i)ans&=b[t[i]-'a']>>i;
            cout<<(ans>>l).count()-(ans>>(r-t.size()+2)).count()<<'\n';
        }
    }
    return 0;
}

::::

6

题目

P5607 [Ynoi2013] 无力回天 NOI2017

题面

共 m 次操作：在编号 x 的集合插入 y 或问编号 x_1 和 x_2 的集合的并的元素个数（m\le10^6，一秒，512MB）。

::::info[做法]

众所周知，开 10^6 的题不一定需要 O(n\log n)，还可能是 O(n\sqrt\frac{n}{w})。

并集有点难做，转化为求交。

对集合大小进行根号分治没有前途，考虑对出现次数进行根号分治：对于出现次数 \le B 的数，枚举这个数字出现的位置更新的复杂度 O(B)。对于出现次数 >B 的数容易用 bitset 做到 O(\frac{m}{Bw})。显然可以平衡到 O(m\sqrt\frac{m}{w})。

注意到会被卡空间，考虑将 bitset 和 gp_hash_table 搞成指针，然后就完了。

这个题的代码写得有点难看，就不放了。 ::::

7

题目

P12525 [Aboi Round 1] 私は雨

题面

给你一个长度为 n 的序列 \{a\}，以及 q 次询问：有多少 i\in [l,r] 且 a_i \in [L,R]，a_i 对 p 取余的结果是 x（强制在线，n,q\le10^5，V\le2\times10^5）。

::::info[做法]

先考虑一个这样的问题：q 次询问，给定 l,r,v_1,v_2,...v_k 查询 \sum_{i=l}^r\sum_{j=1}^k[a_i\le v_k]（q\le10^5，k 之和不超过 5\times10^6）。

考虑直接用 bitset：现将每个数离散化并对每个长度为 S 的块开一个 bitset 记录这个块出现了哪些数，然后再进行前缀异或。因为异或具有差分性，整块直接一个异或搞定，散块再异或上去即可，就可以得到 \left[l,r\right] 之间所有数的位集合。如果每次 k=1 的话，随便手写个前缀 count 就搞定了。但你都 O(\frac{n}{w}) 了，你直接对于 bitset 中 \frac{n}{64} 个 unsigned long long 分别求位数然后直接前缀和，这样就可以 O(\frac{n}{w}) 预处理 O(1) 查了。常数很小，而且还可以轻松做到单点修。

这么整的话 p\ge B 的部分就已经完了。

对于 p<B 的部分，继续考虑 bitset：处理模 p 等于 x 的位置集合；通过对值域进行分块，预处理 [1,kB] 的所有的位置的集合，整块异或处理。将两个位置集合与起来求 count(l,r) 就是值域整块的答案。散块的话直接按 p\ge w 的那部分处理即可。设 n,q,V 同阶，空间复杂度是 O(\frac{n\sqrt n}{w}+nB)，时间复杂度是 O(n\sqrt n+\frac{n^2}{w}+\frac{n^2}{B})，B=100 时我的代码所有点都可以跑进 0.8s。

单点修的话，能复杂度正确的就修，不正确的部分直接每 S 次重构，懒得再写支持单点修的代码了。

代码：

//此处省略快读
constexpr int N=1e5+5,V=2e5;
constexpr int block=300;
constexpr int blockV=420;
int n,m,type,a[N],ca[N],bl[N],L[N/block+5],R[N/block+5],blv[V+2],Lv[V/blockV+5],Rv[V/blockV+5];
bitst t1[N/block+4],tv[V/block+4],t2[102][102],bs;
int sfsadf[1610];int*ans=sfsadf+1;
inline void work(){
    for(int i=0,p=0;i<1600;i+=8){
        ans[i]=pcnt(bs.a[i])+p,ans[i^1]=pcnt(bs.a[i^1]),
        ans[i^2]=pcnt(bs.a[i^2]),ans[i^3]=pcnt(bs.a[i^3]),
        ans[i^4]=pcnt(bs.a[i^4]),ans[i^5]=pcnt(bs.a[i^5]),
        ans[i^6]=pcnt(bs.a[i^6]),ans[i^7]=pcnt(bs.a[i^7]),
        ans[i^1]+=ans[i  ],ans[i^2]+=ans[i^1],ans[i^3]+=ans[i^2],
        ans[i^4]+=ans[i^3],ans[i^5]+=ans[i^4],ans[i^6]+=ans[i^5],
        ans[i^7]+=ans[i^6],p=ans[i^7];
    }
}
int lastans;
int cnt[V+6],sa[V+6];
inline int calc(int x)noexcept{return ans[(x>>6)-1]+pcnt(bs.a[x>>6]<<(63^(x&63)));}
int l,r,p,x;
inline void solve2(int vl,int vr){
    int ml=vl/p*p+x;ml=ml<vl?ml+p:ml;
    for(int i=ml;i<=vr;i+=p)lastans+=calc(sa[i])-calc(sa[i-1]);
}
int vl,vr;
inline void solve1(){
    if(blv[vl]==blv[vr]||blv[vl]+1==blv[vr])return solve2(vl,vr);
    lastans=((tv[blv[vl]]^tv[blv[vr]-1])&t2[p][x]).count(l,r);
    solve2(vl,Rv[blv[vl]]),solve2(Lv[blv[vr]],vr);
}
signed main(){
    cin>>n>>type;
    for(int i=1;i<=block;++i)bl[i]=1;for(int i=block+1;i<=n;++i)bl[i]=bl[i-block]+1;
    for(int i=1;i<=blockV;++i)blv[i]=1;for(int i=blockV+1;i<=V;++i)blv[i]=blv[i-blockV]+1;
    for(int i=1;i<=bl[n];++i)L[i]=(i-1)*block+1,R[i]=min(i*block,n);
    for(int i=1;i<=blv[V];++i)Lv[i]=(i-1)*blockV+1,Rv[i]=min(i*blockV,V);
    for(int i=1;i<=n;++i)cin>>a[i];
    for(int i=1;i<=n;++i)++cnt[a[i]];for(int i=1;i<=V;++i)cnt[i]+=cnt[i-1];
    __builtin_memcpy(sa,cnt,sizeof(int)*(V+2));for(int i=n;i>=1;--i)ca[i]=cnt[a[i]]--;
    for(int i=1,k;i<=bl[n];++i)for(k=L[i],t1[i]=t1[i-1];k<=R[i];++k)t1[i].flip(ca[k]);
    for(int i=1;i<=n;tv[blv[a[i]]].set(i),++i)for(int j=1;j<=100;++j)t2[j][a[i]%j].set(i);
    for(int i=1;i<=blv[V];++i)tv[i]^=tv[i-1];
    cin>>m;
    while(m--){
        cin>>l>>r>>vl>>vr>>p>>x;
        if(type)l^=lastans,r^=lastans,vl^=lastans,vr^=lastans,p^=lastans,x^=lastans;
        if(bl[l]==bl[r]||bl[l]+1==bl[r]){bs.reset();for(int i=l;i<=r;++i)ca[i]?(bs.set(ca[i])):(void());}
        else{
            bs=t1[bl[l]]^t1[bl[r]-1];
            for(int i=L[bl[r]];i<=r;++i)ca[i]?(bs.set(ca[i])):(void());
            for(int i=R[bl[l]];i>=l;--i)ca[i]?(bs.set(ca[i])):(void());
        }work();
        lastans=0,(p<=100)?solve1():solve2(vl,vr);cout<<lastans<<'\n';
    }
    return 0;
}

::::