「CODEVS1191」数轴染色

2014年2月15日3,5028

题目描述 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

<:SECTION id=statistics>

代码

既然只会染成一种颜色。。。lazy标记都不要了

#include<iostream>
#include<cstdio>
using namespace std;
int n,m;
struct datt{
   int l,r,v,lazy;
}t[800001];
void build(int k,int x,int y)
{
	t[k].l=x;t[k].r=y;
	if(x==y){t[k].v=1;return;}
	int mid=(x+y)>>1;
	build(k<<1,x,mid);
	build(k<<1|1,mid+1,y);
	t[k].v=t[k<<1].v+t[k<<1|1].v;
}
void change(int k,int x,int y)
{
	if(t[k].v==0)return;
	int l=t[k].l,r=t[k].r;
	if(l==x&&r==y){t[k].v=0;return;}
	int mid=(l+r)>>1;
	if(mid>=y)change(k<<1,x,y);
	else if(mid<x)change(k<<1|1,x,y);
	else {
	    change(k<<1,x,mid);
	    change(k<<1|1,mid+1,y);
	}
	t[k].v=t[k<<1].v+t[k<<1|1].v;
}
int main()
{
	int x,y;
	scanf("%d%d",&n,&m);
	build(1,1,n);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		change(1,x,y);
		printf("%d\n",t[1].v);
	}
	return 0;
}