线段树——codevs 1690 开关灯

先来一发题目：

1690 开关灯

时间限制: 1 s

空间限制: 128000 KB

题目描述 Description

YYX家门前的街上有N(2<=N<=100000)盏路灯，在晚上六点之前，这些路灯全是关着的，六点之后，会有M(2<=m<=100000)个人陆续按下开关，这些开关可以改变从第i盏灯到第j盏灯的状态，现在YYX想知道，从第x盏灯到第y盏灯中有多少是亮着的(1<=i,j,x,y<=N)

输入描述 Input Description

第 1 行: 用空格隔开的两个整数N和M

第 2..M+1 行: 每行表示一个操作, 有三个用空格分开的整数: 指令号(0代表按下开关，1代表询问状态), x 和 y

输出描述 Output Description

第 1..询问总次数行:对于每一次询问，输出询问的结果

样例输入 Sample Input

4 5
0 1 2
0 2 4
1 2 3
0 2 4
1 1 4
样例输出 Sample Output

1
2

数据范围及提示 Data Size & Hint

一共4盏灯，5个操作，下面是每次操作的状态(X代表关上的，O代表开着的)：

XXXX -> OOXX -> OXOO -> 询问1~3 -> OOXX -> 询问1~4

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 #define N  100000+10
 6 struct node
 7   {
 8       int l,r;
 9       int val;
10       int d;
11   }a[4*N];
12 int n,m,p,x,y;
13 
14 void update(int );
15 void buildtree(int,int,int);
16 void down(int);
17 void add(int,int,int,int,int);
18 int query(int ,int,int,int,int);
19 
20 int main()
21   {
22       scanf("%d%d",&n,&m);
23       buildtree(1,1,n);
24       for(int i=1;i<=m;i++)
25       {
26         scanf("%d%d%d",&p,&x,&y);
27         if(p==0)
28           {
29             add(1,1,n,x,y);
30           }
31         else printf("%d
",query(1,1,n,x,y));
32       }
33     return 0;
34   }
35 void update(int k)
36 {
37     int lch=k*2,rch=(k*2)+1;
38     a[k].val=a[lch].val+a[rch].val;
39 }
40 void buildtree(int k,int l,int r)
41 {
42     a[k].l=l;a[k].r=r;
43     if(l==r)
44     {
45         a[k].val=a[k].d=0;
46         return ;
47     }
48     int mid=(l+r)/2,lch=k*2,rch=(k*2)+1;
49     buildtree(lch,l,mid);
50     buildtree(rch,mid+1,r);
51     update(k);
52  }
53 void down(int k)
54 {
55     int lch=k*2,rch=(k*2)+1;
56     a[lch].d+=a[k].d;
57     a[lch].d%=2;
58     a[lch].val=(a[lch].r-a[lch].l+1)-a[lch].val;
59     a[rch].d+=a[k].d;
60     a[rch].d%=2;
61     a[rch].val=(a[rch].r-a[rch].l+1)-a[rch].val;
62     a[k].d=0;
63 }
64 void add(int k,int l,int r,int x,int y)
65 {
66     if(x<=l&&r<=y)
67     {
68         a[k].d++;
69         a[k].d%=2;
70         a[k].val=(r-l+1)-a[k].val;
71         return;
72     }
73     if(a[k].d)
74       down(k);
75     int mid=(l+r)/2,lch=k*2,rch=(k*2)+1;
76     if(x<=mid)
77       add(lch,l,mid,x,y);
78     if(y>mid)
79       add(rch,mid+1,r,x,y);
80     update(k);
81 }
82 int query(int k,int l,int r,int x,int y)
83 {
84     if(x<=l&&r<=y)
85     {
86         return a[k].val;
87     }
88     if(a[k].d)
89       down(k);
90     int mid=(l+r)/2,lch=k*2,rch=(k*2)+1;
91     int sum=0;
92     if(x<=mid)
93       sum+=query(lch,l,mid,x,y);
94     if(y>mid)
95       sum+=query(rch,mid+1,r,x,y);
96     return sum;  
97 }

View Code