记录编号	343352	评测结果	WWWWWWWWWW
题目名称	Color the Axis	最终得分	0
用户昵称	Yuri	是否通过	未通过
代码语言	C++	运行时间	2.524 s
提交时间	2016-11-09 08:20:58	内存使用	1.76 MiB

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

#define maxn 200010

int n,m;
int cw[maxn];
int section, block[maxn];
bool white[maxn], a[maxn];

void Change(int l,int r){
	int bl=block[l],br=block[r];
	if(bl==br){
		for(int i=l;i<=r;i++){
			if(!a[i]){
				a[i]=1;
				cw[bl]++;
			}
		}
	}
	else{
		if(!white[bl]){
			for(int i=l;block[i]==bl;i++){
				if(!a[i]){
					a[i]=1;
					cw[bl]++;
				}
			}
		}
		for(int i=bl+1;i<br;i++){cw[i]=section;white[i]=1;}
		if(!white[br]){
			for(int i=r;block[i]==br;i--){
				if(!a[i]){
					a[i]=1;
					cw[br]++;
				}
			}
		}
	}
}

int Query(){
	int ans=0;
	for(int i=1;i<=block[n];i++) ans+=cw[i];
	return n-ans;
}

int main(){
	freopen("axis.in","r",stdin);
	freopen("axis.out","w",stdout);
	scanf("%d%d",&n,&m);
	int l,r;
	section = (int)sqrt(n*1.0);
	for(int i=1;i<=n;i++) block[i]=(i-1)/section+1;
	for(int i=1;i<=m;i++){
		scanf("%d%d",&l,&r);
		Change(l,r);
		printf("%d\n",Query());
	}
	//system("pause");
	return 0;
}