题目简述
$n$ 条线段，断点都是正整数且都属于区间 $[1,m]$，Teodor 发现没有一个正整数点在所有的线段上。Sasha 可以向 Teodor 询问若干个整点（但 Sasha 不知道有多少条线段），对于每次询问的点 $x$，Teodor 会回答 $cnt_{x}$ 表示 $x$ 在多少条线段上。求一个最大的集合 $S$ 满足询问 $∀x∈S$ 的 $cnt_x$ 后仍然不能保证没有一个整点满足在所有线段上。只需要输出 $S$ 的大小。
思路
题目中的集合是询问了任意集合内的整点都不能保证这个条件，我们可以反着想 —— 怎样判断「没有一个正整数点在所有的线段上」。
考虑这个问题，可以发现当存在一组整点 $x<y<z$ 满足 $cnt_y<cnt_x$ 且 $cnt_y<cnt_z$ 的时候就可以确定没有一个正整数点在所有的线段上：因为线段是连续的，所以当满足条件时只有可能是中间的点的 $cnt$ 比两边的点大，否则一定有一条线段，覆盖了左边的点和中间的点儿没有右边的点，可以考虑三条线段 $l_1[x,y),\ l_2[x,z],\ l_3(y,z]$。
将每个整点的 $cnt$ 值作为这个位置的值，那么找到两个峰的时候就可以判断不满足条件。那么我们就是要求不能找到两个峰的最大位置集合大小，也就是最长单峰序列长度，只需要正反求两次最长上升子序列即可。其中 $cnt$ 可以差分预处理。
Code
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<climits>
#include<algorithm>
#include<utility>
#include<map>
#include<vector>
#define int long long
using namespace std;
const int MaxN = 100005;
int n, m, a[MaxN], f[MaxN], g[MaxN], ans;
vector<int> number;
inline int Read(){
int num = 0, op = 1;
char ch = getchar();
while(!isdigit(ch)){
if(ch == '-') op = -1;
ch = getchar();
}
while(isdigit(ch)){
num = num * 10 + ch - '0';
ch = getchar();
}
return num * op;
}
signed main(){
n = Read(), m = Read();
for(int i=1; i<=n; i++){
int l = Read(), r = Read();
a[l]++, a[r+1]--;
}
for(int i=1; i<=m; i++)
a[i] += a[i-1];
number.clear();
number.push_back(a[1]);
f[1] = 1;
for(int i=2; i<=m; i++){
if(a[i] >= number.back()){
number.push_back(a[i]);
f[i] = number.size();
}
else{
int pos = upper_bound(number.begin(), number.end(), a[i]) - number.begin();
number[pos] = a[i];
f[i] = pos + 1;
}
}
number.clear();
number.push_back(a[m]);
g[m] = 1;
for(int i = m-1; i>=1; i--){
if(a[i] >= number.back()){
number.push_back(a[i]);
g[i] = number.size();
}
else{
int pos = upper_bound(number.begin(), number.end(), a[i]) - number.begin();
number[pos] = a[i];
g[i] = pos + 1;
}
}
for(int i=1; i<=m; i++)
ans = max(ans, f[i]+g[i]-1);
printf("%lld", ans);
return 0;
}