题解 P3870 【[TJOI2009]开关】

花落丶宸星 · 2018-12-21 20:28:32 · 题解

代码简短的分块

从@Owen_codeisking dalao处学会分块（感谢并膜拜dalao）
这道题是我第3次用c++做分块了转语言的悲哀，发现短过了某一个题解，所以拿出来和大家学习学习。。。

分块，顾名思义就是把数列分成好几段，然后分块操作。其实代码思路就是这样，至于分块的写法我就不多做介绍了，dalao们应该都会吧。。。初一蒟蒻在dalao之间瑟瑟发抖

当时间复杂度最优时，为\sqrt{n},然后操作即可。
过了这道题，还可以去试试LOJ数列分块1-9相信你能AK 代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll L[100010],R[100010],add[100010],a[100010],pos[100010];
void change(int b,int c){
    int p=pos[b],q=pos[c];
    if(p==q){
        for(int i=b;i<=c;i++){
            a[i]=(a[i]+1)%2;
        }
    } else
    {
        for(int i=p+1;i<=q-1;i++) add[i]++;
        for(int i=b;i<=R[p];i++) a[i]=(a[i]+1)%2;
        for(int i=L[q];i<=c;i++) a[i]=(a[i]+1)%2;
    }
}
int find(int b,int c){
    ll ans=0;
    for(int i=b;i<=c;i++){
        if ((a[i]+add[pos[i]])%2==1){
            ans++;
        }
    }
    return ans;
}
int main(){
    ll n,m;
    memset(a,0,sizeof(a));
    scanf("%lld%lld",&n,&m);
    int t=sqrt(n);
    for(int i=1;i<=t;i++){
        L[i]=(i-1)*t+1;R[i]=i*t;
    }
    if (R[t]<n){
        t++;L[t]=R[t-1]+1;R[t]=n;
    }
    for(int i=1;i<=t;i++){
        for(int j=L[i];j<=R[i];j++){
            pos[j]=i;
        }
    }
    for(int i=1;i<=m;i++){
        ll kkk,b,c;
        scanf("%lld%lld%lld",&kkk,&b,&c);
        if(kkk==0){
            change(b,c);
        } else
        {
            printf("%d\n",find(b,c));
        }
    }
    return 0;
}

如果你的运气好，你就能不开O_{2}水过但是好像还是要开的
祝各位AC愉快