[Codevs 1690] 开关灯

USCAO

理论基础

线段树

题目

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

代码

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 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
",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：修改当前节点

转载请注明出处 -- 如有意见欢迎评论