题解 P1840 【Color the Axis_NOI导刊2011提高（05）】
流逝丶
2019-09-19 21:50:06
提供一个比较简单的线段树写法
不用build，ask还有down
一整棵树维护白点的数量，每次change找到精准的区间然后一整个区间都是白点
如果再change的时候发现要访问的区间已经全部覆盖，就可以直接返回，无需再改
输出答案的话，$tr[1]$是区间白点总数，所以答案就是$n-tr[1]$
```cpp
#include<iostream>
#include<cstdio>
#define lson k<<1,l,mid
#define rson k<<1|1,mid+1,r
#define ls k<<1
#define rs k<<1|1
#define mid ((l+r)>>1)
using namespace std;
const int maxn=200005;
int n,m;
int tr[maxn<<2];
inline void update(int k){
tr[k]=tr[ls]+tr[rs];
}
void change(int k,int l,int r,int x,int y){
if(tr[k]==r-l+1)return ;
if(l==x&&y==r){
tr[k]=r-l+1;
return ;
}
if(y<=mid)change(lson,x,y);
else if(x>mid)change(rson,x,y);
else change(lson,x,mid),change(rson,mid+1,y);
update(k);
}
int main(){
scanf("%d%d",&n,&m);
int x,y;
while(m--){
scanf("%d%d",&x,&y);
change(1,1,n,x,y);
printf("%d\n",n-tr[1]);
}
return 0;
}
```