Codeforces Round #468 (Div. 2): F. Teodor is not a liar!（DP）

题意：给出n条线段，这n条线段满足保证不存在一个点使得所有线段都包含它

你现在不知道这n条线段的开头和结尾，甚至也不知道有多少条线段！只知道坐标范围是[1, m]

不过你每给出一个点，电脑都会回答有多少条线段包含它

现要求出一个点的集合，满足①点集里面点尽可能多；

②对于所有点，你都知道有多少条线段覆盖它，但是你仍然不能确定一定不存在某个点所有线段都包含它

（是的这道题非常绕，如果还不懂得话结合样例更佳，看懂了想一想发现还是挺简单的）

先求出[1, m]每个点都有多少条线段包含它，这样可以得出个新的序列

然后对这个新的序列求一个最长（上升-下降）序列就行了，也就是求出个最长山峰序列

这个是个经典的LIS问题，从前往后求一次LIS，从后往前求一次LIS

F[i]表示以i结尾的LIS，G[i]表示以从后往前以i结尾的LIS，答案就是max(F[i]+G[i]-1)

#include<stdio.h>
#include<algorithm>
using namespace std;
typedef struct
{
	int x;
	int y;
}Res;
Res s[100005];
int a[100005], F[100005], b[100005], FF[100005], bet[100005];
int main(void)
{
	int n, m, i, len, l, r, mid, ans;
	scanf("%d%d", &n, &m);
	for(i=1;i<=n;i++)
	{
		scanf("%d%d", &s[i].x, &s[i].y);
		a[s[i].x]++, a[s[i].y+1]--;
	}
	n = m;
	for(i=1;i<=n;i++)
		b[i] = b[i-1]+a[i];
	len = 0;
	for(i=1;i<=n;i++)
	{
		if(len==0 || bet[len]<=b[i])
			bet[++len] = b[i], F[i] = len;
		else
		{
			l = 1, r = len;
			while(l<r)
			{
				mid = (l+r)/2;
				if(bet[mid]<=b[i])
					l = mid+1;
				else
					r = mid;
			}
			bet[r] = b[i];
			F[i] = r;
		}
	}
	len = 0;
	for(i=n;i>=1;i--)
	{
		if(len==0 || bet[len]<=b[i])
			bet[++len] = b[i], FF[i] = len;
		else
		{
			l = 1, r = len;
			while(l<r)
			{
				mid = (l+r)/2;
				if(bet[mid]<=b[i])
					l = mid+1;
				else
					r = mid;
			}
			bet[r] = b[i];
			FF[i] = r;
		}
	}
	ans = 0;
	for(i=1;i<=n;i++)
		ans = max(ans, F[i]+FF[i]-1);
	printf("%d\n", ans);
	return 0;
}