题解 P5057 【[CQOI2006]简单题】

· · 题解

分块题解

看题目，维护一个01序列，支持区间异或，单点查询，强制在线

看到这相信大家都知道了这道题是数据结构，这道题线段树，树状数组，分块都能AC

线段树O(nlogn) 大常数，树状数组O(nlogn) 小常数，分块O（n\sqrt{n}）大常数。

分块在更多场合有用 (指骗分场合)

与线段树相比，分块的pushdown操作就是完全暴力，但线段树的pushdown或者pushup往往需要观察题目性质，或是巧妙转换维护的数据来让答案可维护，从这点上来说，分块思维难度比线段树小

考试时面对看起来像数据结构题的东西，如果意识到正解很难写时间不够调不出来，打个分块耐心调块长才是明智之举

上代码

#include<bits/stdc++.h>

using namespace std ;

const int MAXN = 100010;
int n,m;
struct Block{
    int l,r;
    int tag;
}blo[1000];
int fab[MAXN],a[MAXN],sq,bctr;

void set_up(){
    sq = sqrt(n);
    bctr = n/sq;
    if(n%sq) ++bctr;
    for(int i=1;i<=n;i++)
        fab[i] = (i-1)/sq+1;
    for(int i=1;i<bctr;i++){
        blo[i].l = (i-1) * sq + 1;
        blo[i].r = i * sq; 
    }
    blo[bctr].l = (bctr-1) * sq + 1;
    blo[bctr].r = n;
}

void pushdown(int x){
    for(int i=blo[x].l;i<=blo[x].r;i++)
        a[i] ^= 1;
    blo[x].tag = 0;
}

void change (int x,int y){
    if(fab[x] == fab[y]){
        if(blo[fab[x]].tag) pushdown(fab[x]);
        for(int i=x;i<=y;i++)
            a[i] ^= 1;
        return;
    }
    if(blo[fab[x]].l != x){
        if(blo[fab[x]].tag) pushdown(fab[x]);
        for(int i=x;i<=blo[fab[x]].r;i++)
            a[i] ^= 1;
    }
    else blo[fab[x]].tag ^= 1;
    if(blo[fab[y]].r != y){
        if(blo[fab[y]].tag) pushdown(fab[y]);
        for(int i=blo[fab[y]].l;i<=y;i++)
            a[i] ^= 1;
    }
    else blo[fab[y]].tag ^= 1;
    for(int i=fab[x]+1;i<=fab[y]-1;i++)
        blo[i].tag ^= 1;
    return;
}

int ask(int x){
    return a[x]^blo[fab[x]].tag;
}

int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    set_up();
    for(int i=1;i<=m;i++){
        int t,x,y;
        cin>>t;
        if(t == 1){
            cin>>x>>y;
            change(x,y);
        }
        if(t == 2){
            cin>>x;
            cout<<ask(x)<<endl;
        }
    }
    return 0;
}

TAG ： SIN_XIII ⑨