codevs 1191 线段树

这道题算是非常基本的线段树了，采用线段树的原因是在线段树上查找到某个区间的复杂度是对数级别的。

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 using namespace std;
 5 
 6 const int N = 200001;
 7 int n, m;
 8 
 9 struct Node 
10 {
11     int l, r, sum;
12 } node[N << 2];
13 
14 void pushup( int i )
15 {
16     node[i].sum = node[i << 1].sum + node[i << 1 | 1].sum;
17 }
18 
19 void build( int i, int l, int r )
20 {
21     node[i].l = l, node[i].r = r, node[i].sum = r - l + 1;
22     if ( l == r ) return ;
23     int mid = ( l + r ) >> 1;
24     build( i << 1, l, mid );
25     build( i << 1 | 1, mid + 1, r );
26 }
27 
28 void update( int i, int l, int r )
29 {
30     if ( node[i].sum == 0 ) return ;
31     if ( node[i].l == l && node[i].r == r )
32     {
33         node[i].sum = 0;
34         return ;
35     }
36     int mid = ( node[i].l + node[i].r ) >> 1;
37     if ( r <= mid )
38     {
39         update( i << 1, l, r );
40     }
41     else if ( l > mid )
42     {
43         update( i << 1 | 1, l, r );
44     }
45     else
46     {
47         update( i << 1, l, mid );
48         update( i << 1 | 1, mid + 1, r );
49     }
50     pushup(i);
51 }
52 
53 int main ()
54 {
55     while ( scanf("%d%d", &n, &m) != EOF )
56     {
57         build( 1, 1, n );
58         while ( m-- )
59         {
60             int x, y;
61             scanf("%d%d", &x, &y);
62             update( 1, x, y );
63             printf("%d
", node[1].sum);
64         }
65     }
66     return 0;
67 }