题解 P5057 【[CQOI2006]简单题】

· · 题解

吸氧分块做法

看到TJ里好像没有用分块做的，于是蒟蒻就来发一条用bitset分块的TJ

分块，是一种时间复杂度带根号的做法。虽然劣于线段树和树状数组，导致此题分块需要吸氧才能跑过，但是个人觉得分块代码比线段树好打多了，也比树状数组更容易理解...

题意分析

一个01数组，给出两个操作，分别是区间翻转01和单点查询.要求输出查询结果

思路1-暴力

看到题目，首先想到的就是直接暴力大模拟，实测大模拟加快读可拿80pts 暴力核心代码(\text{qin}是快读)：

int ccf,a[N],poo;
signed main()
{
    qin >> n >> m;
    while(m--)
    {
        qin >> ccf;
        if(ccf == 1)
        {
            qin >> l >> r;
            for(reg int i = l;i <= r;i++)
            {
                a[i] = !a[i];
            }
        }
        else
        {
            qin >> poo;
            printf("%d\n",a[poo]);
        }
    }
    return 0;
}

思路2-优雅的暴力-分块

分块其实真的是一种优雅的暴力

分块的思路

由于暴力明显会T掉，我们可以把数组中的n个元素分成\sqrt{n}个有着\sqrt{n}个元素的小块，即开\sqrt{n}个大小为\sqrt{n}的\text{bitset}。说到\text{bitset}，下面介绍一下\text{bitset}的一些用法：

**$\text{bitset}$的声明** ```cpp std::bitset<[size]> s;//size为bitset大小，s为bitset变量名（当然可以开数组） ``` **$\text{bitset}$的某些用法(默认已使用标准命名空间)** ```cpp s.test(i)//查询s中的第i位是否为1，是返回true，否返回false s.set([i])//将s的第i位设置为1，不填i则将整个bitset全部设为1 s.reset([i])//将s的第i位设置为0，不填i则将整个bitset全部设为0 s.flip([i])//将s的第i位取反，不填i则将整个bitset全部取反（比用for循环异或稍微快一点） ``` 看题目数据范围，发现: $$1 \leq n \leq 10^5, 1 \leq m \leq 5 × 10^5$$ ~~窝当时把数据范围看成$50\%$的了...还导致我发了个贴qwq~~ 于是我们就可以直接定义每一块的大小： ```cpp const int blk_sze = 320; bitset<blk_sze> s[319];//每一块下标从0开始，块的编号下标也从0开始 ``` 做好了准备，了解了前置知识，我们终于可以开始写代码了$\text{AwA}

以下是完整代码

#include <cstdio>
#include <bitset>
#define reg register
using namespace std;
int n,m,l,r,op,pos,lid,rid,llid,rrid,blkid,in_blkid;
const int blk_sze = 320;//320个1块(0~319) 320~639 640~959......
bitset<blk_sze> s[319];
int main()
{
    scanf("%d%d",&n,&m);//读入
    for(reg int i = 1;i <= m;i++)
    {
        scanf("%d",&op);//读入
        if(op == 1)//操作1
        {
            scanf("%d%d",&l,&r);//读入左端点和右断点
            l--;
            r--;//由于我们的块的下标和块内下标都是从0开始，而读入数据默认是从1开始，所以这里l和r都要-1
            lid = l / blk_sze;
            rid = r / blk_sze;//计算左端点所处块，右端点所处块的编号
            for(reg int j = lid + 1;j < rid;j++)
            {
                s[j].flip();
            }//把左右端点之间的块全部直接整块取反
            llid = l % blk_sze;//左边界在左端点所处块内的位置
            rrid = r % blk_sze;//右边界在右端点所处块内的位置
            if(lid != rid)//如果左右边界不在同一块中
            {
                for(reg int j = llid;j < blk_sze;j++)
                {
                    s[lid].flip(j);
                }
                for(reg int j = 0;j <= rrid;j++)
                {
                    s[rid].flip(j);
                }
            }
            else//如果左右端点在一个块中
            {
                for(reg int j = llid;j <= rrid;j++)
                {
                    s[lid].flip(j);//这里的lid也可以改成rid，是一样的
                }
            }//进行这样的判断是为了防止左右端点在同一块的情况导致那整个块都被直接取反
        }
        else//操作2
        {
            scanf("%d",&pos);//读入位置
            pos--;
            blkid = pos / blk_sze;//pos所处块的编号
            in_blkid = pos % blk_sze;//pos所处块的块内位置
            printf("%d\n",s[blkid].test(in_blkid));//输出答案
        }
    }
    return 0;
}

最终结果

后言

可能用打标记开数组的那种分块能不吸氧A掉此题？我没试过...不知道有没有神犇能写出来试试\text{QwQ}?