洛谷P5057 [CQOI2006]简单题 bitset一秒过八亿

题面

大家好,我是一个连分块都不会不想打的蒟蒻,于是我就用$bitset$水过了这题

另外,小蒟蒻其实不是很熟悉$bitset$,如果写得不优,还请大佬轻D

en…让我们理性分析一下时间复杂度:$O(\frac{nm}{w})$,$w$为64,那也到了接近$8e8$的复杂度…可以说是相当硬核的$AC$了.

本题的题意相当清晰,只需要提供$2$种操作:

$1$.区间异或

$2$.求某一位上的值

很明显都是可以用$bitset$来做的,这里讲讲$bitset$的基本操作(也可以去看洛谷日报:

头文件

都9102年了还不用万能库?

#include<bitset>

定义

std::bitset<位数>bit;

初始化

bit.set();//全部变成1
bit.reset();//全部变成0

位运算

和正常位运算一样

求某1位的值

和数组一致

然后回到这题,对于区间异或,我们可以先全部赋值为1,然后先右移使$bitset$中正好有$r-l+1$个1,再将它左移(l-1)位($bitset$也是从0开始),与原来的$bitset$进行异或操作就行了

询问?直接输出$s[i-1]$(从$0$
开始)

然后这题就愉快地水过啦!

另外自带大常数的同学们,$O_3$和$Ofast$可以在$O_2$的基础上再减小50%的常数哦(逃

代码:

// luogu-judger-enable-o2
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
#define getchar() (p1==p2 and (p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<23],*p1=buf,*p2=buf;
//fread快读优化模板拿走不谢
inline void read(int &a){
    a=0;
    char c=getchar();
    while(c>57 or c<48)c=getchar();
    while(47<c and c<58){
        a=a*10+c-48;
        c=getchar();
    }
}
int n,m,opt,l,r;
std::bitset<100000>bit,ha;//bit为原来的bitset
//乱取的变量名是因为真的想不到能AC(逃)
int main(){
    read(n);read(m);
    for(int i=1;i<=m;++i){
        read(opt);
        if(opt&1){
            read(l);read(r);
            int lon=r-l+1;
            int p=100000-lon;
            ha.set();
            ha>>=p;
            //右移至只剩r-l+1个1
            ha<<=(l-1);//移到l-r的位置
            bit^=ha;
        }
        else{
            read(l);
            puts(bit[l-1]?"1":"0");
            //bitset用print会警告,不过也无所谓
        }
    }
    return 0;
}