bitset 基本操作复习

yummy · 2022-11-09 23:11:37 · 题解

更棒的 bitset 操作，尽在本题解中！

传统 bitset

观察到这题的数据范围是 10^5，而且全是 01 串，因此联想到 O(n^2w^{-1}) 的 bitset。（本文中 w 均表示字长，默认 64）。

传统的 bitset 可以借助位运算轻松地维护区间置 0、区间置 1、区间翻转，时间复杂度均为 O(n/w)。而且这三者代码极为接近，一般写完一个稍微改改就能得到另一个。

同时借助 __builtin_popcountll 函数（时间复杂度 O(\log w)，我们可以写出区间数 1 的代码。

难点

但是区间数连续 1 数并不好维护——哪怕维护同一 int64 的前缀、后缀 1 数量可以用 lowbit 和 __lg 解决，同块连续 1 数量也没有对应的位运算手段。

因此我们对于这种操作我们只能放弃位运算，直接将一块内所有情形全部预处理出左侧 1 数、右侧 1 数、连续 1 数。

这也就导致对于这种运算我们选取的块长不能是 64 了（我选的 16，也就是一大块变四小块，要是有人不怕麻烦可以选 21,21,22），但是前几种操作我们依然可以选 64。

注意事项 & 调试技巧

unsigned long long 溢出是有定义的，long long 溢出算 UB。
当你要取二进制某一位时请写成 1ull<<x（而非 1<<x），否则会导致溢出。
大部分同学用小端法 bitset 存储（也就是 2^0 位对应 seq_0），但是左移右移运算仍然建立在大端法基础上，因此两种记法不要弄混。
（适用于所有题目） 你认为是难点、最容易出错的地方可能反而没那么容易出错，比如这道题我一直在 4 操作上找问题找了一下午，最后发现是 0 操作有一处 l,r 写成 bl,br 了。

#include<bits/stdc++.h>
using namespace std;
const int Rsh=6,B=1<<Rsh,B4=16,Bmx=65535;
//块长是2的Rsh次方也就是B，特别地，4操作块长为 B4，块内最大值Bmx
int n,m,cb[1<<16],l1[1<<16],r1[1<<16];
unsigned long long a[1565],op[64][64];
//op[l][r]为二进制第l..r位均为 1 的二进制数，为减小位运算打错概率我设计成这样
void set0(int l,int r)//[l,r]
{
    int bl=l>>Rsh,br=r>>Rsh;
    l&=B-1;r&=B-1;
    if(bl==br)//特判同一块
    {
        a[bl]&=~op[l][r];
        return;
    }
    a[bl]&=~op[l][B-1];
    a[br]&=~op[0][r];
    for(int i=bl+1;i<br;i++)
        a[i]=0;
}
void set1(int l,int r)
{
    int bl=l>>Rsh,br=r>>Rsh;
    l&=B-1;r&=B-1;
    if(bl==br)
    {
        a[bl]|=op[l][r];
        return;
    }
    a[bl]|=op[l][B-1];
    a[br]|=op[0][r];
    for(int i=bl+1;i<br;i++)
        a[i]=-1ull;
}
void rev(int l,int r)
{
    int bl=l>>Rsh,br=r>>Rsh;
    l&=B-1;r&=B-1;
    if(bl==br)
    {
        a[bl]^=op[l][r];
        return;
    }
    a[bl]^=op[l][B-1];
    a[br]^=op[0][r];
    for(int i=bl+1;i<br;i++)
        a[i]^=-1ull;
}
#define BPL __builtin_popcountll 
int countbit(int l,int r)
{
    int bl=l>>Rsh,br=r>>Rsh;
    l&=B-1;r&=B-1;
    if(bl==br)
        return BPL(a[bl]&op[l][r]);
    int tot=BPL(a[bl]&op[l][B-1])+BPL(a[br]&op[0][r]);
    for(int i=bl+1;i<br;i++)
        tot+=BPL(a[i]);
    return tot;
}
int combo(int l,int r)
{
    if((l>>4)==(r>>4))//其实这不是必须，见后面代码
        return cb[(a[l>>Rsh]&op[l&(B-1)][r&(B-1)])>>(l&(B-1))];
    int bl=l>>Rsh,br=r>>Rsh,overall=0,mxr=0;
    //overall记录当前所有连续1最大值，mxr记录当前有几个连续的1
    unsigned long long RealAbl=a[bl],RealAbr=a[br];
    //为节省讨论，我们将干扰清空，完事重新写入
    a[bl]&=op[l&(B-1)][B-1];a[br]&=op[0][r&(B-1)];
    for(int i=bl;i<=br;i++)
    {
        for(int j=1;j<=4;j++)
        {
            unsigned long long v=a[i]<<(B-j*B4)>>(3*B4);//请注意，这里涉及大端法和小端法的区别
            if(v==Bmx)//如果这块全 1
            {
                overall=max(overall,mxr+B4);
                mxr+=B4;
            }
            else
            {
                overall=max(overall,max(mxr+r1[v],cb[v]));
                mxr=l1[v];
            }
        }
    }
    a[bl]=RealAbl;a[br]=RealAbr;
    return overall;
}
int main()
{
    for(int i=0;i<B;i++)//预处理 op数组
    {
        op[i][i]=1ull<<i;
        for(int j=i+1;j<B;j++)
            op[i][j]=op[i][j-1]|(1ull<<j);
    }
    for(int i=0;i<(1<<B4);i++)
    {
        if(i&1)r1[i]=r1[i>>1]+1;//大端法右侧 1 个数
        else r1[i]=0;
        cb[i]=max(cb[i>>1],r1[i]);//块内最大连续 1 个数
        for(int j=i;j&(1<<B4-1);j=(j<<1)^(1<<B4))l1[i]++;//大端法左侧 1 个数，反正不是瓶颈，多个log无所谓了
    }
    scanf("%d%d",&n,&m);
    unsigned long long tmp;
    for(int i=0;i<n;i++)
    {
        scanf("%llu",&tmp);
        a[i>>Rsh]|=tmp<<(i&(B-1));
    }
    int op,l,r;
    for(;m;m--)
    {
        scanf("%d%d%d",&op,&l,&r);
        if(op==0)set0(l,r);
        if(op==1)set1(l,r);
        if(op==2)rev(l,r);
        if(op==3)printf("%d\n",countbit(l,r));
        if(op==4)printf("%d\n",combo(l,r));
    }
    return 0;
}