题目描述 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
/* 线段树维护数轴上的黑点数，一次染色相当于一次区间修改 区间修改就意味着lazy的标记和下放，下方是很费时间的 想对于每个点lazy标记最多下放一次，所以下放过的lazy不清零，而是变为2，以后只下放lazy==1的即可 */ #include<iostream> #include<cstdio> using namespace std; const int maxn=200010; int n,m,opx,opy; struct node{ int l,r,v,lazy; }tr[maxn<<4]; void build(int l,int r,int k){ tr[k].l=l;tr[k].r=r;tr[k].v=1; if(l==r)return; int mid=(l+r)>>1; build(l,mid,k<<1); build(mid+1,r,k<<1|1); tr[k].v=tr[k<<1].v+tr[k<<1|1].v; } void update(int k){ tr[k].lazy=2; tr[k].v=0; if(tr[k].l==tr[k].r)return; update(k<<1); update(k<<1|1); } void change(int l,int r,int k){ if(tr[k].l==l&&tr[k].r==r){ tr[k].v=0; if(tr[k].lazy==0)tr[k].lazy=1; return; } if(tr[k].lazy==1)update(k); int mid=(tr[k].l+tr[k].r)>>1; if(r<=mid)change(l,r,k<<1); else if(l>mid)change(l,r,k<<1|1); else { change(l,mid,k<<1); change(mid+1,r,k<<1|1); } tr[k].v=tr[k<<1].v+tr[k<<1|1].v; } int main(){ scanf("%d%d",&n,&m); build(1,n,1); for(int i=1;i<=m;i++){ scanf("%d%d",&opx,&opy); change(opx,opy,1); printf("%d ",tr[1].v); } }