记录编号	471528	评测结果	AAAAAAAAAAAAAAAAAAAAA
题目名称	[HAOI 2014]贴海报	最终得分	100
用户昵称	~玖湫~	是否通过	通过
代码语言	C++	运行时间	0.010 s
提交时间	2017-11-06 16:40:56	内存使用	0.49 MiB

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>

using namespace std;

#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r

const int M=4010;

int n,num,ans,cnt;
int L[M],R[M],tmp[M];
int kd[M<<2],adda[M<<2];
bool vis[M];

inline int read(){

	int x=0,f=1; char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
	return x*f;

}

inline void pushdown(int rt){

	int ls=rt<<1,rs=rt<<1|1;

	adda[ls]=adda[rs]=adda[rt];

	kd[ls]=kd[rs]=adda[rt];

	adda[rt]=0;

}

inline void change(int s,int t,int zhi,int rt,int l,int r){

	if(s<=l&&r<=t) { kd[rt]=zhi; adda[rt]=zhi; return ; }

	int mid=l+r>>1;

	if(adda[rt]) pushdown(rt);

	if(s<=mid) change(s,t,zhi,lson);

	if(t>mid) change(s,t,zhi,rson);

}

inline void PushDown(int rt,int l,int r){

	if(l==r) return ;

	int mid=l+r>>1;

	if(adda[rt]) pushdown(rt);

	PushDown(lson); PushDown(rson);

}

inline void work(int rt,int l,int r){

	if(l==r) {

		if(!vis[kd[rt]]) ++ans,vis[kd[rt]]=1;

		return ;

	}	int mid=l+r>>1;

	work(lson);	   work(rson);

}

int main(){

	freopen("ha14d.in","r",stdin);
	freopen("ha14d.out","w",stdout);

	n=read(); n=read(); int xx,yy;
	for(int i=1;i<=n;++i){

		L[i]=read();		 R[i]=read();
		tmp[++cnt]=L[i];     tmp[++cnt]=R[i];

		tmp[++cnt]=L[i]-1;

		tmp[++cnt]=R[i]+1;

	}	sort(tmp+1,tmp+cnt+1);  

	num=unique(tmp+1,tmp+cnt+1)-tmp;  vis[0]=1;

	for(int i=1;i<=n;++i){

		L[i]=lower_bound(tmp+1,tmp+num,L[i])-tmp;
		R[i]=lower_bound(tmp+1,tmp+num,R[i])-tmp;

		//cout<<L[i]<<" "<<R[i]<<endl;

	}	

	for(int i=1;i<=n;++i) change(L[i],R[i],i,1,1,num-1);

	PushDown(1,1,num-1);   work(1,1,num-1);

	printf("%d\n",ans);

	return 0;

}