记录编号	130202	评测结果	AWWWAAAAAA
题目名称	[HAOI 2014]贴海报	最终得分	70
用户昵称	Dot_Dot	是否通过	未通过
代码语言	C++	运行时间	0.001 s
提交时间	2014-10-21 21:04:54	内存使用	0.89 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>
#define QAQ 30005
using namespace std;
struct point{int val,x;}dot,a[QAQ];
bool comp(point x,point y){return x.val<y.val;}
bool vis[QAQ];
int n,m,ans;
int p[QAQ][2],f[QAQ];
int find(int i){return f[i]==-1?i:f[i]=find(f[i]);}
void lisanhua()
{
	int lisan=1,temp=a[0].val;//lisan=lisanzuobiao
	for(int i=0;i<2*m;i++)
	{
		if(a[i].val!=temp)
		{
			lisan++;
			temp=a[i].val;
			if(i!=0&&a[i-1].x>0)
				if((a[i-1].val+1)!=a[i].val)
					lisan++;
		}
		if(a[i].x<0)
			p[-a[i].x-1][0]=lisan;
		else p[a[i].x-1][1]=lisan;
	}
}
void begin()
{
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;i++)
	{
		scanf("%d%d",&p[i][0],&p[i][1]);
		a[i<<1].x=-i-1;
		a[(i<<1)+1].x=i+1;
		a[i<<1].val=p[i][0];
		a[(i<<1)+1].val=p[i][1];
	}
	sort(a,a+2*m,comp);
	lisanhua();
}
void cover()
{
	int l,r;
	bool flag=false;
	for(int i=m-1;i>=0;i--)
	{
		l=find(p[i][0]);
		for(int j=p[i][1];j>=p[i][0];j=r-1)
		{
			r=find(j);
			if(!vis[r])
			{
				vis[r]=true;
				flag=true;
			}
			if(l!=r) f[r]=l;
		}
		if(flag) ans++;
		flag=false;
	}
}
int main()
{
	freopen("ha14d.in","r",stdin);
	freopen("ha14d.out","w",stdout);
	begin();
	memset(f,-1,sizeof(f));
	memset(vis,false,sizeof(vis));
	cover();
	printf("%d\n",ans);
	return 0;
}