首页 > 代码库 > AC日记——开关灯 codevs 1690

AC日记——开关灯 codevs 1690

开关灯

 

思路:

  线段树;

  bool懒标记维护;

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

 

来,上代码:

#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;#define maxn 100005struct TreeNodeType {    int l,r,dis,lit,mid,flag;};struct TreeNodeType tree[maxn<<2];int n,m;inline void in(int &now){    char Cget=getchar();now=0;    while(Cget>9||Cget<0) Cget=getchar();    while(Cget>=0&&Cget<=9)    {        now=now*10+Cget-0;        Cget=getchar();    }}void tree_build(int now,int l,int r){    tree[now].l=l,tree[now].r=r,tree[now].lit=r-l+1;    if(l==r) return ;    tree[now].mid=l+r>>1;    tree_build(now<<1,l,tree[now].mid);    tree_build(now<<1|1,tree[now].mid+1,r);}inline void tree_down(int now){    tree[now<<1].flag^=1,tree[now<<1|1].flag^=1;    tree[now<<1].dis=tree[now<<1].lit-tree[now<<1].dis;    tree[now<<1|1].dis=tree[now<<1|1].lit-tree[now<<1|1].dis;    tree[now].flag=0;}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^=1;        return ;    }    if(tree[now].flag) tree_down(now);    if(l>tree[now].mid) tree_change(now<<1|1,l,r);    else if(r<=tree[now].mid) tree_change(now<<1,l,r);    else    {        tree_change(now<<1,l,tree[now].mid);        tree_change(now<<1|1,tree[now].mid+1,r);    }    tree[now].dis=tree[now<<1].dis+tree[now<<1|1].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<<1|1,l,r);    else if(r<=tree[now].mid) tree_query(now<<1,l,r);    else return tree_query(now<<1,l,tree[now].mid)+tree_query(now<<1|1,tree[now].mid+1,r);}int main(){    in(n),in(m);int op,u,v;    tree_build(1,1,n);    for(;m--;)    {        in(op),in(u),in(v);        if(op) printf("%d\n",tree_query(1,u,v));        else tree_change(1,u,v);    }    return 0;}

 

AC日记——开关灯 codevs 1690