T1191 数轴染色 codevs

http://codevs.cn/problem/1191/

时间限制: 1 s

空间限制: 128000 KB

题目等级 : 黄金 Gold

题目描述 Description

在一条数轴上有N个点，分别是1～N。一开始所有的点都被染成黑色。接着
我们进行M次操作，第i次操作将[Li,Ri]这些点染成白色。请输出每个操作执行后
剩余黑色点的个数。

输入描述 Input Description

输入一行为N和M。下面M行每行两个数Li、Ri

输出描述 Output Description

输出M行，为每次操作后剩余黑色点的个数。

样例输入 Sample Input

10 3
3 3
5 7
2 8

样例输出 Sample Output

9
6
3

数据范围及提示 Data Size & Hint

数据限制
对30%的数据有1<=N<=2000,1<=M<=2000
对100%数据有1<=Li<=Ri<=N<=200000,1<=M<=200000

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 
 6 using namespace std;
 7 
 8 int M,N,li,ri;
 9 int tree[1000000];
10 
11 void build(int x,int l,int r)
12 {
13     if(l==r)
14     {
15         tree[x]=1;
16         return ;
17     }
18     int midd=(l+r)/2;
19     build(x*2,l,midd);
20     build(x*2+1,midd+1,r);
21     tree[x]=tree[x*2]+tree[x*2+1];
22 }
23 
24 void change(int x,int l,int r,int ll,int rr)
25 {
26     if(l>rr||r<ll||tree[x]==0)
27         return ;
28     if(l>=ll&&r<=rr)
29     {
30         tree[x]=0;
31         return ;
32     }
33     int midd=(l+r)/2;
34     change(x*2,l,midd,ll,rr);
35     change(x*2+1,midd+1,r,ll,rr);
36     tree[x]=tree[x*2]+tree[x*2+1];
37     return ;
38 }
39 
40 int main()
41 {
42     cin>>N>>M;
43     build(1,1,N);
44     for(int i=1;i<=M;i++)
45     {
46         cin>>li>>ri;
47         change(1,1,N,li,ri);
48         cout<<tree[1]<<endl;
49     }
50     return 0;
51 }

——每当你想要放弃的时候，就想想是为了什么才一路坚持到现在。