记录编号	155703	评测结果	AAAAAAAAAAAAAAAAAAAAA
题目名称	[HAOI 2014]贴海报	最终得分	100
用户昵称	HouJikan	是否通过	通过
代码语言	C++	运行时间	0.042 s
提交时间	2015-03-29 22:16:53	内存使用	19.94 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <list>
#include <vector>
#include <ctime>
#include <functional>
#define pritnf printf
#define scafn scanf
#define For(i,j,k) for(int i=(j);i<=(k);(i)++)
using namespace std;
typedef long long LL;
typedef unsigned int Uint; 
const int INF=500*10010;
//==============struct declaration==============
struct intervals{
  int s,e;
  int color;
};
//==============var declaration=================
const int MAXN=10100;
const double eps=1e-6;
#define y1 y
int n,T,top,y1,y2,c,cnt;
unsigned short int id[10000100],color[MAXN*10];
int t[MAXN*6];//,pos[MAXN*6];
intervals Interval[MAXN];
bool Exist[MAXN];
//==============function declaration============
void paint(int o,int l,int r);
void countcolor(int o,int l,int r);
//==============main code=======================
int main()
{  
#define FILE__
#ifdef FILE__
  freopen("ha14d.in","r",stdin);
  freopen("ha14d.out","w",stdout); 
#endif
  scanf("%d",&T);
  {
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
      scanf("%d%d",&Interval[i].s,&Interval[i].e);
      t[i*2-1]=Interval[i].s;t[i*2]=Interval[i].e;
    }
    sort(t+1,t+1+n*2);top=0;
    for(int i=1;i<=n*2;i++){
      if (t[i]==t[i+1]) continue;
      id[t[i]]=++top;
      //pos[top]=t[i];
      if (t[i+1]!=t[i]+1&&i!=n*2)
        id[t[i]+1]=++top;
      //pos[top]=t[i]+1;
    }
    memset(color,0,sizeof(color));
    for(int i=1;i<=n;i++){
       y1=id[Interval[i].s];y2=id[Interval[i].e];c=i;
       //printf("%d %d\n",y1,y2);
       paint(1,1,top);
    }
    //for(int i=1;i<=top*3;i++)
    //  printf("%d ",color[i]);
    memset(Exist,false,sizeof(false));
    cnt=0;
    countcolor(1,1,top);
    for(int i=1;i<=n;i++)
      if (Exist[i]) cnt++;
    printf("%d\n",cnt);
  }
  return 0;
}
//================fuction code====================
void paint(int o,int l,int r)
{
  if (y1<=l&&r<=y2){
    color[o]=c;
    return;
  }
  int lc=o*2,rc=o*2+1,m=(l+r)>>1;
  if (color[o])
      color[lc]=color[rc]=color[o];
  color[o]=0;
  if (y1<=m)
    paint(lc,l,m);
  if (m<y2)
    paint(rc,m+1,r);
}
void countcolor(int o,int l,int r)
{
  int lc=o*2,rc=o*2+1,m=(l+r)>>1;
  if (color[o]){
    Exist[color[o]]=true;
    //printf("[%d %d]:%d\n",pos[l],pos[r],color[o]);
    return;
  }
  if (l==r) return;
  countcolor(lc,l,m);
  countcolor(rc,m+1,r);
}