P3870 [TJOI2009] 开关 题解

WydnksqhbD · 2024-03-08 20:40:22 · 题解

P3870 [TJOI2009] 开关 题解

前言

本题解的代码是 @QWQ_123 巨佬写的，在此鸣谢。搬运已经经过同意。

思路

众所周知，暴力出奇迹。

那么我们可以打出暴力代码：

#include<bits/stdc++.h>
using namespace std;
int arr[1000005];
int main()
{
    int n,m;
    cin>>n>>m;
    while(m--)
    {
        int c,a,b;
        cin>>c>>a>>b;
        if(c)
        {
            int sum=0;
            for(int i=a;i<=b;i++)
            {
                sum+=arr[i];
            }
            cout<<sum<<endl;
        }
        else
        {
            for(int i=a;i<=b;i++)
            {
                arr[i]^=1;
            }
        }
    }
    return 0;
}

但是这样会喜提 TLE。

不过众所周知，C++ 有个好东西叫 bitset。

bitset 就是将 8 个 bool 类型的变量压入一个 Byte，使得常数除以了 32（每次可以改 32 个。有的是 64。）。

这样 O(nm) 的暴力变为了 O(\frac{nm}{w}) 的暴力（w=32）。

所以可以卡过去（10^5\times10^5\div32=312500000）。

代码中为了区间操作，使用了一些 bitset 有关的函数，详见 bitset - OI Wiki。

• 头文件：#include<bitset>。
• 定义：bitset<S>b，其中 S 表示大小，b 就是名字。
• 运算符：
• • b[i]：表示访问 b_i。
• • b[i]==/!=b[j]：比较 b_i,b_j 是否一样。
• 函数：
• • count()：返回 1 的数量。
• • test()：等同于 []。
• • size()：返回 bitset 的大小。

代码

达成史上最短代码。

#include<bits/stdc++.h>
using namespace std;
int n,m;
bitset<100010>s,s1;
int main()
{
    s1.set();cin>>n>>m;
    while(m--)
    {
        int opt,l,r;cin>>opt>>l>>r;
        //修改和查询都是利用 bitset 的函数来写的。>>、<< 是位运算。 
        if(opt==0)s^=((s1>>(100010-r+l-1))<<(l-1));//修改操作，区间异或。 
        else cout<<(s&((s1>>(100010-r+l-1))<<(l-1))).count()<<endl;//count() 查询有几个 1。 
    }
    return 0;
}