记录编号	343376	评测结果	AAAAAAAAAA
题目名称	Color the Axis	最终得分	100
用户昵称	Bravo ChaoS	是否通过	通过
代码语言	C++	运行时间	1.114 s
提交时间	2016-11-09 08:50:35	内存使用	6.26 MiB

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

class input
{
public:
    input& operator >> (int& x)
    {
        char c=' ';x=0;
        while(c<'0' || c>'9') c=getchar();
        while(c>='0' && c<='9') x=x*10+c-'0',c=getchar();
        return *this;
    }
}in;

const int maxn=200010;

int n,m,t;

struct Node
{
    int l,r,wt;
    bool vis;
    Node(int l,int r,int wt,bool vis): l(l),r(r),wt(wt),vis(vis){}
    Node(){}
}node[maxn<<2];

void built(int x,int l,int r)
{
    node[x]=Node(l,r,0,0);
    if(l==r) return;
    int mid=l+(r-l>>1);
    built(x<<1,l,mid);
    built(x<<1|1,mid+1,r);
}

void modify(int x,int l,int r)
{
    Node& nd=node[x];
    if(nd.vis) {return;}
    if(nd.l==nd.r)
    {
        nd.vis=1;nd.wt=1;
        return;
    }
    if(nd.l==l && nd.r==r)
    {
        t=nd.wt;
        nd.wt=nd.r-nd.l+1;nd.vis=1;
        return;
    }
    int mid=nd.l+(nd.r-nd.l>>1),lt=x<<1,rt=x<<1|1;
    if(mid<l) modify(rt,l,r);
    else if(mid+1>r) modify(lt,l,r);
    else modify(lt,l,mid),modify(rt,mid+1,r);
    nd.wt=node[lt].wt+node[rt].wt;
    if(nd.r-nd.l+1<=nd.wt) nd.vis=1;
}

int main()
{
    freopen("axis.in","r",stdin);
    freopen("axis.out","w",stdout);
    in>>n>>m;
    built(1,1,n);
    for(int l,r;m--;)
    {
        in>>l>>r;modify(1,l,r);
        printf("%d\n",n-node[1].wt);
    }
    
    return 0;
}