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

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
//#include<ctime>
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);
//    cout<<x<<' '<<l<<' '<<r<<endl;
    if(l==r) return;
    int mid=l+(r-l>>1);
    built(x<<1,l,mid);
    built(x<<1|1,mid+1,r);
}

int modify(int x,int l,int r)//return wt
{
    int sum=0;
    Node& nd=node[x];
    if(nd.vis) {return 0;}
    if(nd.l==nd.r)
    {
        nd.vis=1;nd.wt=1;
        return 1;
    }
    if(nd.l==l && nd.r==r)
    {
        t=nd.wt;
        nd.wt=nd.r-nd.l+1;nd.vis=1;
        return nd.wt-t;
    }
    int mid=nd.l+(nd.r-nd.l>>1);
    if(mid<l) sum=modify(x<<1|1,l,r);
    else if(mid+1>r) sum=modify(x<<1,l,r);
    else sum=modify(x<<1,l,mid)+modify(x<<1|1,mid+1,r);
    nd.wt+=sum;
    if(nd.r-nd.l+1<=nd.wt) nd.vis=1;
//        cout<<x<<' '<<nd.l<<' '<<nd.r<<' '<<nd.wt<<endl;
    return sum;
}

int main()
{
//    int a=clock();
    freopen("axis.in","r",stdin);
    freopen("axis.out","w",stdout);
    in>>n>>m;
    built(1,1,n);
//    cout<<"================"<<endl;
    for(int l,r;m--;)
    {
        in>>l>>r;modify(1,l,r);
        printf("%d\n",n-node[1].wt);
    }
//    int b=clock();
//    cout<<"time:  "<<b-a<<endl;
    
    return 0;
}