[Codevs 1690] 开关灯-白红宇

[Codevs 1690] 开关灯

阅读量：5150 次

发布时间：2019-06-13

本文共 2134 字，大约阅读时间需要 7 分钟。

USCAO

理论基础

线段树

题目

Portal： http://codevs.cn/problem/1690/

代码

1 #include
      
        2 #include
       
         3 #include
        
          4 #define mid ((L+R)/2) 5 #define lc (rt<<1) 6 #define rc (rt<<1|1)  7 #define maxn 500000 8 using namespace std; 9 10 struct TreeNode{11     int sum,lazy;12 }Tree[maxn*4];13 14 void maintain(int rt){15     Tree[rt].sum = Tree[lc].sum + Tree[rc].sum;16 }17 18 void pushdown(int rt,int L,int R){19     if(Tree[rt].lazy){20         Tree[lc].lazy ^= 1;21         Tree[rc].lazy ^= 1;22         Tree[lc].sum = (mid-L+1)-Tree[lc].sum;23         Tree[rc].sum = (R-mid)-Tree[rc].sum;24         Tree[rt].lazy = 0;25     }26 }27 28 void build(int rt,int L,int R){29     Tree[rt].lazy = 0;30     if(L == R){31         Tree[rt].sum = 0;32     }else{33         build(lc,L,mid);34         build(rc,mid+1,R);35         36         maintain(rt);37     }38 }39 40 void modify(int rt,int L,int R,int qL,int qR){41     if(Tree[rt].lazy) pushdown(rt,L,R);42     if(qL <= L && R <= qR){43         Tree[rt].lazy ^= 1;44         if(Tree[rt].lazy){45             Tree[rt].sum = (R-L+1)-Tree[rt].sum;46         }47     }else{48         if(qL <= mid) modify(lc,L,mid,qL,qR);49         if(qR > mid) modify(rc,mid+1,R,qL,qR);50         51         maintain(rt);52     }53 }54 55 int query(int rt,int L,int R,int qL,int qR){56     if(Tree[rt].lazy) pushdown(rt,L,R);57     if(qL <= L && R <= qR) return Tree[rt].sum;58     else{59         int ans = 0;60         if(qL <= mid) ans += query(lc,L,mid,qL,qR);61         if(qR > mid) ans += query(rc,mid+1,R,qL,qR);62         return ans;63     }64 }65 66 int main(){67     68     int n,m,a,b,c;69     scanf("%d%d",&n,&m);70     build(1,1,n);71     for(int i = 0;i < m;i++){72         scanf("%d%d%d",&a,&b,&c);73         if(a) printf("%d\n",query(1,1,n,b,c));74         else modify(1,1,n,b,c);75     }76     77     return 0;78 }

View Code

lazy：此处值为1证明需要翻转否则不用。

lc：Left Child左子树

rc：参考lc

L&R：表示当前区间左右端点

qL&qR：表示询问区间左右端点

sum：当前结点值，即区间内开灯总和

build：初始化函数

modify：修改用函数

query：查询用函数

pushdown：配合lazy使用

maintain：修改当前节点