记录编号	343381	评测结果	AAAAAAAAAA
题目名称	Color the Axis	最终得分	100
用户昵称	__stdcall	是否通过	通过
代码语言	C++	运行时间	0.628 s
提交时间	2016-11-09 08:55:28	内存使用	5.52 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <cctype>

using namespace std;

int n,m;

struct IO {
    static const int BUFSZ = 500000;
    char buf[BUFSZ];
    int idx;
    IO(){ idx = BUFSZ; }
    void readfile() {
        fread( buf , 1 , BUFSZ , stdin );
    }
    char getch() {
        if( idx == BUFSZ ) {
            readfile(); idx = 0;
        }
        return buf[idx++];
    }
    int getnum() {
        int num = 0;
        char ch;
        while( isspace(ch=getch()) );
        do {
            num *= 10;
            num += ch-'0';
        }while( isdigit(ch=getch()) );
        return num;
    }
};

IO io;

struct SGT {
    int setv[800010];
    int sumv[800010];
    int left,right;
    void build(){ buildtree(1,1,n); }
    void buildtree( int o , int L , int R ) {
        if( L == R ) {
            setv[o] = sumv[o] = 1;
            return;
        }
        int M = L+(R-L)/2;
        int lc = o<<1; int rc = lc|1;
        buildtree(lc,L,M);
        buildtree(rc,M+1,R);
        setv[o] = -1; // -1表示没有设置setv的值
        sumv[o] = sumv[lc] + sumv[rc];
    }
    void set0( int L , int R ) {
        left=L; right=R;
        settree(1,1,n);
    }
    void settree( int o , int L , int R ) {
        if( setv[o] == 0 ) return;
        if( L >= left && R <= right ) {
            setv[o] = sumv[o] = 0;
            return;
        }
        int M = L+(R-L)/2;
        int lc = o<<1; int rc = lc|1;
        if( left <= M ) settree(lc,L,M);
        if( right > M ) settree(rc,M+1,R);
        sumv[o] = sumv[lc] + sumv[rc];
    }
    int query() {
        return sumv[1];
    }
};

SGT sgt;

int main() {
    freopen( "axis.in" , "r" , stdin );
    freopen( "axis.out" , "w" , stdout );
    n = io.getnum(); m = io.getnum();
    sgt.build();
    for( int i = 0 ; i < m ; ++i ) {
        int l = io.getnum();
        int r = io.getnum();
        sgt.set0(l,r);
        printf( "%d\n" , sgt.query() );
    }
    return 0;
}