AC日记——开关灯 codevs 1690

开关灯

思路：

　　线段树；

　　bool懒标记维护；

　　更新区间时是区间总值减去当前值；

来，上代码：

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

#define maxn 100005

struct TreeNodeType {

    int l,r,dis,lit,mid,flag;

};

struct TreeNodeType tree[maxn<<];

int n,m;

inline void in(int &now)

{

    char Cget=getchar();now=;

    while(Cget>''||Cget<'') Cget=getchar();

    while(Cget>=''&&Cget<='')

    {

        now=now*+Cget-'';

        Cget=getchar();

    }

}

void tree_build(int now,int l,int r)

{

    tree[now].l=l,tree[now].r=r,tree[now].lit=r-l+;

    if(l==r) return ;

    tree[now].mid=l+r>>;

    tree_build(now<<,l,tree[now].mid);

    tree_build(now<<|,tree[now].mid+,r);

}

inline void tree_down(int now)

{

    tree[now<<].flag^=,tree[now<<|].flag^=;

    tree[now<<].dis=tree[now<<].lit-tree[now<<].dis;

    tree[now<<|].dis=tree[now<<|].lit-tree[now<<|].dis;

    tree[now].flag=;

}

void tree_change(int now,int l,int r)

{

    if(tree[now].l==l&&tree[now].r==r)

    {

        tree[now].dis=tree[now].lit-tree[now].dis;

        tree[now].flag^=;

        return ;

    }

    if(tree[now].flag) tree_down(now);

    if(l>tree[now].mid) tree_change(now<<|,l,r);

    else if(r<=tree[now].mid) tree_change(now<<,l,r);

    else

    {

        tree_change(now<<,l,tree[now].mid);

        tree_change(now<<|,tree[now].mid+,r);

    }

    tree[now].dis=tree[now<<].dis+tree[now<<|].dis;

}

int tree_query(int now,int l,int r)

{

    if(tree[now].l==l&&tree[now].r==r) return tree[now].dis;

    if(tree[now].flag) tree_down(now);

    if(l>tree[now].mid) tree_query(now<<|,l,r);

    else if(r<=tree[now].mid) tree_query(now<<,l,r);

    else return tree_query(now<<,l,tree[now].mid)+tree_query(now<<|,tree[now].mid+,r);

}

int main()

{

    in(n),in(m);int op,u,v;

    tree_build(,,n);

    for(;m--;)

    {

        in(op),in(u),in(v);

        if(op) printf("%d\n",tree_query(,u,v));

        else tree_change(,u,v);

    }

    return ;

}