记录编号	343276	评测结果	AAAAAAAAAA
题目名称	Color the Axis	最终得分	100
用户昵称	L_in	是否通过	通过
代码语言	C++	运行时间	4.955 s
提交时间	2016-11-09 07:22:41	内存使用	5.78 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 200010
#define mid ((l+r)>>1)
#define L rt<<1,l,mid
#define R rt<<1|1,mid+1,r
using namespace std;
int a[maxn<<2];//白点的个数 
int lazy[maxn<<2];
int n,m,ans;
void push_down(int rt,int l,int r){
	a[rt<<1]=(mid-l+1)*lazy[rt];
	a[rt<<1|1]=(r-mid)*lazy[rt];
	lazy[rt<<1]=lazy[rt];
	lazy[rt<<1|1]=lazy[rt];
	lazy[rt]=0;
}
void change(int rt,int l,int r,int s,int t,int w){
	if(s<=l&&t>=r){
		lazy[rt]=w;
		a[rt]=(r-l+1)*w;
		return;
	}
	if(lazy[rt])push_down(rt,l,r);
	if(s<=mid)change(L,s,t,w);
	if(t>mid)change(R,s,t,w);
	a[rt]=a[rt<<1]+a[rt<<1|1];
}
int query(int rt,int l,int r,int s,int t){
	if(s<=l&&t>=r)return a[rt];
	if(lazy[rt])push_down(rt,l,r);
	if(t<=mid)return query(L,s,t);
	if(s>mid)return query(R,s,t);
	return query(L,s,t)+query(R,s,t);
}
int main(){
	freopen("axis.in","r",stdin);
	freopen("axis.out","w",stdout);
	scanf("%d%d",&n,&m);
	int x,y;
	ans=n;
	for(int i=1;i<=m;i++){
		scanf("%d%d",&x,&y);
		int k=query(1,1,n,x,y);
		ans-=(y-x+1-k);
		change(1,1,n,x,y,1);
		printf("%d\n",ans);
	}
	fclose(stdin);fclose(stdout);
	return 0;
}