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 /*基本思路：利用线段树的区间操作，把叶节点都设为1，更改的时候设置为0，就可以了*/ 2 #include
           
             3 using namespace std; 4 #include
            
              5 struct node{ 6     long long int l,r,val; 7     node *child[2]; 8     int delta; 9 }*root=NULL;10 int n,m,a,b;11 void update(node *cur)12 {13     cur->val=cur->child[0]->val+cur->child[1]->val;14 }15 void bulid(node *&cur,int l,int r)16 {17     if(l>r) return ;18     cur=new node;19     cur->l=l;cur->r=r;20     cur->delta=1;21     if(l==r)22     {23         cur->child[0]=cur->child[1]=NULL;24         cur->val=1;/*设置为1，表示一个叶节点是一个黑点*/25         return;26     }27     int mid=(l+r)/2;28     bulid(cur->child[0],l,mid);29     bulid(cur->child[1],mid+1,r);30     update(cur);/*统计出了每个区间的黑点数*/31 }32 void down(node *cur)/*标志的下传*/33 {34     cur->child[0]->val=cur->child[0]->delta=cur->child[1]->val=cur->child[1]->delta=0;35 }36 void change(node *cur,int l,int r)37 {38     if(l<=cur->l&&cur->r<=r)39     {40         cur->val=0;41         cur->delta=0;/*给子区间的标志*/42         return;43     }44     if(!cur->delta) down(cur);/*必不可少的必不可少的成分，一开始没过去就是因为这个地方，当把这个区间val赋值为0时，他的子区间没有修改，下次访问他的子区间，会得出错误答案，所以设置一个懒惰标志，用来下传*/45     int mid=(cur->l+cur->r)/2;46     if(l<=mid) change(cur->child[0],l,r);47     if(r>mid) change(cur->child[1],l,r);48     update(cur);49 }50 /*long long int query(node *cur,int l,int r)51 {52     if(l<=cur->l&&cur->r<=r)53     {54         cout<
             
              val<
              
               val;56     }57     int ans=0;58     int mid=(cur->l+cur->r)/2;59     if(l<=mid) ans+=query(cur->child[0],l,r);60     if(r>mid) ans+=query(cur->child[1],l,r);61     cout<
               
                <
                
                 val);75 }76 return 0;77 }78 }