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

分类标签 Tags

裸的线段树。

一定要记住如果整个区间都是0了一定要return

啊啊啊啊啊啊啊啊啊啊

 

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 using namespace std; 6 const int MAXN=200001; 7 void read(int & n) 8 { 9     char c='+';int x=0;int flag=0;10     while(c<'0'||c>'9')11     {    if(c=='-')    flag=1;    c=getchar();    }12     while(c>='0'&&c<='9')13     {    x=x*10+(c-48);    c=getchar();}14     flag==1?n=-x:n=x;15 }16 int n,m;17 struct node18 {19     int l,r,w;20 }tree[MAXN*4];21 void update(int k)22 {23     tree[k].w=tree[k<<1].w+tree[k<<1|1].w;24 }25 void build_tree(int ll,int rr,int k)26 {27     28     tree[k].l=ll;tree[k].r=rr;29     if(ll==rr)30     {31         tree[k].w=1;32         return ;33     }    34     int mid=(ll+rr)>>1;35     build_tree(ll,mid,k<<1);36     build_tree(mid+1,rr,k<<1|1);37     update(k);38 }39 void interval_change(int k,int ql,int qr)40 {41     if(tree[k].w==0)42     return ;43     if(ql<=tree[k].l&&qr>=tree[k].r)44     {45         tree[k].w=0;46         return ;47     }48     int mid=(tree[k].l+tree[k].r)>>1;49     if(ql<=mid)50         interval_change(k<<1,ql,qr);51     if(qr>mid)52         interval_change(k<<1|1,ql,qr);53     update(k);54 }55 int main()56 {57     read(n);read(m);58     build_tree(1,n,1);59     for(int i=1;i<=m;i++)60     {61         int x,y;62         read(x);read(y);63         interval_change(1,x,y);64         printf("%d\n",tree[1].w);65     }66     return 0;67 }