题目描述

　　一个二维平面上有\(n\)个梯形，满足：

　　　所有梯形的下底边在直线\(y=0\)上。

　　　所有梯形的上底边在直线\(y=1\)上。

　　　没有两个点的坐标相同。

　　你一次可以选择任意多个梯形，必须满足这些梯形两两重叠，然后删掉这些梯形。

　　问你最少几次可以删掉所有梯形。

　　\(n\leq {10}^5\)

题解

　　先把坐标离散化。

　　定义\(A\)为所有梯形组成的集合。

　　我们定义\(A\)上的严格偏序：两个梯形\(a<b\)当且仅当\(a\)与\(b\)不重叠且\(a\)在\(b\)的左边。

　　那么每次删掉的矩形就是一条反链。

　　所以这道题求的是最小反链覆盖。

　　根据Dilworth定理的对偶定理，有：最小反链覆盖数\(=\)最长链长度

　　所以我们只用求最长链长度就好了。

　　这个东西可以DP做。

　　\(a11,a12,a21,a22\)分别代表一个梯形的上底边的两个端点的横坐标，下底边的两个端点的横坐标

　　可以把所有梯形按\(a11\)排序，维护一个以\(a12\)为关键字的堆，把队中的元素取出以\(a22\)位置，\(f_j\)为值插入到树状数组中，然后在树状数组中查询答案。

　　时间复杂度：\(O(n\log n)\)

代码

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

#include<utility>

using namespace std;

typedef pair<int,int> pii;

priority_queue<pii,vector<pii>,greater<pii> > q;

struct p

{

	int a11,a12,a21,a22;

};

p a[100010];

int cmp(p a,p b)

{

	return a.a11<b.a11;

}

int f[100010];

int c[100010];

int m=0;

int d[200010];

void add(int x,int v)

{

	for(;x<=m;x+=x&-x)

		c[x]=max(c[x],v);

}

int query(int x)

{

	int s=0;

	for(;x;x-=x&-x)

		s=max(s,c[x]);

	return s;

}

int main()

{

#ifndef ONLINE_JUDGE

	freopen("b.in","r",stdin);

	freopen("b.out","w",stdout);

#endif

	int n,i;

	scanf("%d",&n);

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

	{

		scanf("%d%d%d%d",&a[i].a11,&a[i].a12,&a[i].a21,&a[i].a22);

		d[++m]=a[i].a21;

		d[++m]=a[i].a22;

	}

	sort(d+1,d+m+1);

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

	{

		a[i].a21=lower_bound(d+1,d+m+1,a[i].a21)-d;

		a[i].a22=lower_bound(d+1,d+m+1,a[i].a22)-d;

	}

	sort(a+1,a+n+1,cmp);

	int ans=0;

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

	{

		q.push(pii(a[i].a12,i));

		while(!q.empty()&&q.top().first<a[i].a11)

		{

			pii x=q.top();

			q.pop();

			add(a[x.second].a22,f[x.second]);

		}

		f[i]=query(a[i].a21)+1;

		ans=max(ans,f[i]);

	}

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

	return 0;

}