题解 CF930C

好题啊好题。

定义 \(a_i\) 为有多少个区间包含 \(i\)。

拍脑袋一想，当且仅当存在顺序的三个坐标 \((i,j,k)\) 满足 \(a_i>a_j\) 且 \(a_j<a_l\) 时，可以确定没有数被所有区间包含。

这个结论很简单，因为如果存在，则 \(a\) 序列必定为一个“山峰”。而如果出现上面这种情况，说明有“山谷”。

所以我们可以用树状数组求出 \(f_i\) 表示以 \(i\) 结尾的最长不下降子序列，\(g_i\) 表示以 \(i\) 开头的最长不上升子序列。

那么答案为 \(ans=\max\limits_{i=1}^{n-1}\left(f_i+\max\limits_{j=i+1}^{n}g_j\right)\)。

复杂度 \(O(n\log n)\)。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m,a[N],f[N],g[N],c[N];
int lbt(int x){return x&(-x);}
void update(int i,int k){for(;i<=n;i+=lbt(i))c[i]=max(c[i],k);}
int getmax(int i){int res=0;for(;i;i-=lbt(i))res=max(res,c[i]);return res;}
int main(){
  ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  cin>>m>>n;
  for(int i=1;i<=m;++i){
    int l,r;cin>>l>>r;
    ++a[l];--a[r+1];
  }
  for(int i=1;i<=n;++i)a[i]+=a[i-1];
  for(int i=1;i<=n;++i)++a[i];
  for(int i=1;i<=n;++i){
    f[i]=getmax(a[i])+1;
    update(a[i],f[i]);
  }
  for(int i=1;i<=n;++i)c[i]=0;
  int ans=0,maxn=0;
  for(int i=n;i>=1;--i){
    g[i]=getmax(a[i])+1;
    update(a[i],g[i]);
    ans=max(ans,f[i]+maxn);
    maxn=max(maxn,g[i]);
  }
  cout<<ans<<endl;
  return 0;
}