题外话:说谎的人的英文竟然是 liar 一直以为是 lier
wssb
依旧首先看题luogu codeforces
看完题之后发现有点抽象啊,于是我们开始手搓样例
但是我们发现这个好像是线段覆盖状物
然后我们注意到这个一定是和每个点又几个线段覆盖有关的,因为如果我连这个都不知道那么这个题也别想做了.
于是我们考虑使用差分预处理每个点被几个线段给覆盖了
然后 \(\Theta(n)\) 地计算出每个点被覆盖的次数
我们不难发现,形如这样的
$ 1,2,2,1,1,2,2,1$
序列我们最多只能选 \(1,2,2,2,2,1\) 或者 \(1,1,2,2,1\) 这样的子序列而无法出现选出这样的子序列 \(1,2,2,1,2,2,1\)
这是因为当我们选择上面前两种子序列时,我们无法判断这个序列有没有从中间断开,
也就是说我们无法判断是否存在一个点满足题意
而对于后者,由于中间出现了一个点比旁边的点的数值更小,我们一定可以断定这个点没有被所有的线段覆盖
因为它左边的线段无法覆盖到它而且右边的也无法覆盖它
这是我们重新审视一下这两个目标子序列,发现它们都是先不下降,再不上升,即单峰
那么我们应该如何去完成这道题呢?
显然,我们可以定义两个 \(dp1\) 和 \(dp2\) 来帮助我们求答案
\(dp1_i\) 就表示前 \(i\) 个数(注意: 包括 \(i\) 自己)的最长不下降子序列长度
\(dp2_i\) 就表示后 \(n-i+1\) 个数(注意: 包括 \(i\) 自己)的最长不上升子序列长度
最后的答案显然就是 \(\max\limits_{1\le i \le n} dp1_i+dp2_i-1\) 注意到这里要 \(-1\) 是因为我们刚才定义时两边均包含了 \(i\) 这个数需要被减掉.
现在的目标就是求 \(dp1\) 和 \(dp2\) 这两个数组了.考虑贪心的去求时间复杂度 \(\Theta(n\text{ }log_2n)\) 于是这道题就被我们解决了
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m,a[N],d[N],dp1[N],dp2[N],ans;
vector<int> g;int main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){int l,r;scanf("%d%d",&l,&r);d[l]++;d[r+1]--;}for(int i=1;i<=m;i++){a[i]=a[i-1]+d[i];}for(int i=1;i<=m;i++){vector<int>::iterator pos=upper_bound(g.begin(),g.end(),a[i]);if(pos==g.end()){g.push_back(a[i]);}else{*pos=a[i];}dp1[i]=g.size();}reverse(a+1,a+m+1);g.clear();for(int i=1;i<=m;i++){vector<int>::iterator pos=upper_bound(g.begin(),g.end(),a[i]);if(pos==g.end()){g.push_back(a[i]);}else{*pos=a[i];}dp2[i]=g.size();}reverse(dp2+1,dp2+m+1);for(int i=1;i<=m;i++)ans=max(ans,dp1[i]+dp2[i]-1);printf("%d\n",ans);return 0;
}