记录编号	345112	评测结果	AAAAAATATT
题目名称	Color the Axis	最终得分	70
用户昵称	Janis	是否通过	未通过
代码语言	C++	运行时间	6.255 s
提交时间	2016-11-10 20:06:00	内存使用	10.68 MiB

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;

const int maxn = 200000 + 10;
const int oo = ~(1<<31);
struct SEG{
	int l,r,lc,rc;
	int lazy,lazyv;
	int sumv;
	void clear(int a,int b){
		l = a, r = b;
		lc=rc=-1;
		sumv=0;
		lazy = lazyv = 0;
	}
}tree[maxn<<1];
int n,m,p;
int tot(1);
int a[maxn];

inline int read()
{
	int x,f=1;
	char ch;
	while(ch=getchar(),!isdigit(ch)){
		if(ch=='-')f=-1;
		if(ch==EOF)return -1;
	}
	x=ch-48;
	while(ch=getchar(),isdigit(ch))x=x*10+ch-48;
	return x*f;
}
int build(int x,int y){
	int p = tot++;
	SEG& now = tree[p];
	now.clear(x,y);
	if(x < y){
		int k = (x+y)>>1;
		now.lc = build(x,k);
		now.rc = build(k+1,y);
		now.sumv = tree[now.lc].sumv + tree[now.rc].sumv;
	}
	return p;
}	
void pushdown(int x){
	if(x == -1)return;
	SEG& now = tree[x];
	if(now.lazy){
		tree[now.lc].lazy = tree[now.rc].lazy = now.lazy;
		tree[now.lc].lazyv = tree[now.rc].lazyv = now.lazyv;
		tree[now.lc].sumv = now.lazyv*(tree[now.lc].r-tree[now.lc].l+1);
		tree[now.rc].sumv = now.lazyv*(tree[now.rc].r-tree[now.rc].l+1);
		now.lazy = 0;
	}
}
void Set(int root,int x,int y){
	if(root == -1)return;
	SEG& now = tree[root];
	if(x > now.r || y < now.l)return;
	if(x <= now.l && now.r <= y){
		now.lazy = 1;
		now.lazyv = 1;
		now.sumv = (now.r-now.l+1)*now.lazyv;
	}
	else{
		pushdown(root);
		Set(now.lc,x,y);
		Set(now.rc,x,y);
		now.sumv = tree[now.lc].sumv+tree[now.rc].sumv;	
	}
}
int Sum(int root,int x,int y){
	if(root == -1)return 0;
	SEG& now = tree[root];
	if(x > now.r || y < now.l)return 0;
	if(x <= now.l && now.r <= y)return now.sumv;
	else{
		pushdown(root);
		int sum(0);
		sum += Sum(now.lc,x,y);
		sum += Sum(now.rc,x,y);
		return sum;
	}
}
int main()
{
	#ifndef DEBUG
		string FileName="axis";
		freopen((FileName+".in").c_str(),"r",stdin);
		freopen((FileName+".out").c_str(),"w",stdout);
	#endif
	//scanf("%d",&n);	scanf("%d",&m);
	n=read();m=read();
	build(1,n);
	for(int i = 1; i <= m; i++){
		int x,y;
		//scanf("%d%d",&x,&y);
		x=read();y=read();
		Set(1,x,y);
		printf("%d\n",n-Sum(1,1,n));
	}
}