记录编号	343284	评测结果	AAAAAAAAAA
题目名称	Color the Axis	最终得分	100
用户昵称	河北交通广播992小强来了	是否通过	通过
代码语言	C++	运行时间	4.347 s
提交时间	2016-11-09 07:26:34	内存使用	5.16 MiB

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
const int maxn=200900;
int sum[maxn<<2],n,m,lazy[maxn<<2];
void Build(int,int,int);
void change(int,int,int,int,int);
void Update(int);
int getsum(int,int,int,int,int);
int main()
{
	freopen("axis.in","r",stdin);
	freopen("axis.out","w",stdout);
	scanf("%d%d",&n,&m);
	Build(1,1,n);
	for(int i=1;i<=m;i++)
	{
		int x,y;scanf("%d%d",&x,&y);
		change(x,y,1,1,n);printf("%d\n",getsum(1,n,1,1,n));
	}
	return 0;
}
void Build(int rt,int l,int r)
{
	if(l==r){sum[rt]=1;return;}
	int mid=(l+r)>>1;
	Build(lson);Build(rson);
	sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void change(int s,int t,int rt,int l,int r)
{
	if(s<=l&&t>=r){sum[rt]=0;lazy[rt]=1;return;}
	if(lazy[rt])Update(rt);
	int mid=(l+r)>>1;
	if(s<=mid)change(s,t,lson);
	if(t>mid)change(s,t,rson);
	sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void Update(int rt)
{
	lazy[rt]=0;lazy[rt<<1]=1;lazy[rt<<1|1]=1;
	sum[rt<<1]=0;sum[rt<<1|1]=0;
}
int getsum(int s,int t,int rt,int l,int r)
{
	if(s<=l&&t>=r)return sum[rt];
	if(lazy[rt])Update(rt);
	int mid=(l+r)>>1;
	if(t<=mid)return getsum(s,t,lson);
	if(s>mid)return getsum(s,t,rson);
	return getsum(s,t,lson)+getsum(s,t,rson);
}