记录编号	344529	评测结果	AAAAAAAAAA
题目名称	Color the Axis	最终得分	100
用户昵称	404	是否通过	通过
代码语言	C++	运行时间	1.165 s
提交时间	2016-11-10 11:13:43	内存使用	14.02 MiB

#include<bits/stdc++.h>
#define lc rt<<1
#define rc rt<<1|1
using namespace std;
const int maxn=200020;
struct node{int l,r,c,num,lz;}t[maxn*4];
int n,m;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
inline void up(int rt)
{
	if(t[lc].c==t[rc].c)t[rt].c=t[lc].c;
	else t[rt].c=2;
	t[rt].num=t[lc].num+t[rc].num;
}
void build(int l,int r,int rt)
{
     t[rt].l=l,t[rt].r=r;
     if(l==r){t[rt].c=0,t[rt].lz=-1,t[rt].num=0;return;}
     build(l,(l+r)>>1,lc);build((l+r)/2+1,r,rc);
     up(rt);
}
void change(int l,int r,int rt,int xl,int xr)
{
	if(t[rt].c==1)return;
	if(xl<=l&&xr>=r){t[rt].c=1,t[rt].num=r-l+1;return;}
	int mid=(l+r)>>1;
	if(xr<=mid)change(l,mid,lc,xl,xr);
	else if(xl>mid)change(mid+1,r,rc,xl,xr);
	else change(l,mid,lc,xl,mid),change(mid+1,r,rc,mid+1,xr);
	up(rt);
}
int main()
{
    freopen("axis.in","r",stdin);
    freopen("axis.out","w",stdout);
    scanf("%d%d",&n,&m);
    build(1,n,1);
    while(m--)
    {
	    int l,r;
	    l=read(),r=read();
	    change(1,n,1,l,r);
	    printf("%d\n",n-t[1].num);
    }return 0;
}
/*
10 3
3 3
5 7
2 8
*/