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 <cstdio>
 2 using namespace std;
 3 
 4 int n,m,tree[800100],x,y;
 5 
 6 void build(int x,int l,int r)        //建树
 7 {
 8     if (l==r)
 9     {
10         tree[x]=1;
11         return;
12     }
13     int m=(l+r)/2;
14     build(x*2,l,m);
15     build(x*2+1,m+1,r);
16     tree[x]=tree[x*2]+tree[x*2+1];
17 }
18 
19 void change(int x,int l,int r,int ql,int qr)      //单点修改
20 {
21     if (l>qr||r<ql||tree[x]==0) return;
22     if (l>=ql&&r<=qr) 
23     {
24         tree[x]=0;
25         return;
26     }
27     int m=(l+r)/2;
28     change(x*2,l,m,ql,qr);
29     change(x*2+1,m+1,r,ql,qr);
30     tree[x]=tree[x*2]+tree[x*2+1];
31     return;
32 }
33 
34 int main()
35 {
36     scanf("%d%d",&n,&m);
37     build(1,1,n);
38     for (int i=1; i<=m; i++)
39     {
40         scanf("%d%d",&x,&y);
41         change(1,1,n,x,y);
42         printf("%d
",tree[1]);             //直接输出和
43     }
44     return 0;
45 }