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

#include <cstdio>
#include <iostream>
#include <cmath>
using namespace std;
const int _maxn=400010;
int tree[_maxn<<2],n,m,M;
bool vis[_maxn<<2];
void push(int x){
	x+=M;
	tree[x]=1;
	x>>=1;
	while(x){
		tree[x]=tree[x<<1]+tree[(x<<1)+1];
		x>>=1;
	}
}
void update(int u,int v){
	int y1=u+M-1,y2=v+M+1;
	while(y1^y2^1){
		if(~y1&1){
			vis[y1^1]=true;
			tree[y1^1]=0;
		}
		if(y2&1){
			vis[y2^1]=true;
			tree[y2^1]=0;
		}
		y1>>=1;y2>>=1;
	}
	u+=M;v+=M;
	while(u!=v){
		if(!vis[u])
			tree[u]=tree[u<<1]+tree[(u<<1)+1];
		u>>=1;
		if(!vis[v])
			tree[v]=tree[v<<1]+tree[(v<<1)+1];
		v>>=1;
	}
	while(u){
		if(!vis[u])
			tree[u]=tree[u<<1]+tree[(u<<1)+1];
		u>>=1;
	}
}
int main(){
	freopen("axis.in","r",stdin);
	freopen("axis.out","w",stdout);
	int x,y;
	scanf("%d%d",&n,&m);
	M=1<<(int)log2(n+1)+1;
	for(int i=1;i<=n;i++)
		push(i);
	for(int i=1;i<=m;i++){
		scanf("%d%d",&x,&y);
		update(x,y);
		printf("%d\n",tree[1]);
	}
	return 0;
}