记录编号	344994	评测结果	AAAAAAAAAA
题目名称	Color the Axis	最终得分	100
用户昵称	Phosphorus15	是否通过	通过
代码语言	C++	运行时间	1.347 s
提交时间	2016-11-10 18:04:29	内存使用	0.28 MiB

#include <iostream>
#include <cstdio>

//using std::cin;
using std::cout;
using std::endl;

struct input{
  input & operator >>(int &i){
    i = 0;
    char c = getchar();
    while(not(c>='0'&&c<='9')) c = getchar();
    while(c>='0'&&c<='9'){i = i * 10 + (c-'0'); c = getchar();}
    return *this;
  }
}cin;

struct SegNode{
  SegNode * left;
  SegNode * right;
  int l;
  int r;
  int black;
  SegNode(){
    left = right = NULL;
  }
};

struct SegTree{
  SegNode * root;
  SegTree(int n){
    root = new SegNode();
    root->l = 1;
    root->r = n;
  }
  void build(int l,int r,SegNode * node){
    if(l>r)
      return ;
    node->l = l;
    node->r = r;
    if(l==r){
      node->black = 1;
      return ;
    }else{
      int mid = ((l+r)>>1);
      node->left = new SegNode();
      node->right = new SegNode();
      build(l,mid,node->left);
      build(mid+1,r,node->right);
      node->black = node->left->black + node->right->black;
    }
  }
  int query(int l,int r,int ql,int qr,SegNode *node){
    //cout<<"seg query "<<l<<" "<<r<<endl;
    //cout<<"node info "<<node->l<<" "<<node->r<<endl;
    int result = 0;
    if(node->black == 0 or l > r)
      return 0;
    //cout<<"continue"<<endl;
    if(node->l==node->r){
      if(node->black!=0){node->black = 0;return 1;}
      return 0;
    }
    int mid = node->left->r;
    if(ql>mid){
      result += query(mid+1,r,ql,qr,node->right);
    }else if(qr<=mid){
      result += query(l,mid,ql,qr,node->left);
    }else{
      result += (query(l,mid,ql,qr,node->left) + query(mid+1,r,ql,qr,node->right));
    }
    node->black = node->left->black + node->right->black;
    return result;
  }
};

int main(int argc,char ** argv){
  freopen("axis.in","r",stdin);
  freopen("axis.out","w+",stdout);
  int n,m,total,l,r;
  cin>>n>>m;
  SegTree tree = SegTree(n);
  tree.build(1,n,tree.root);
  total = n;
  for(int x=0;x not_eq m;x++){
    cin>>l>>r;
    total -= tree.query(l,r,l,r,tree.root);
    //cout<<total<<endl;
    printf("%d\n",total);
  }
  return 0;
}