随机排列的最长上升子序列长度的期望是 \(O(\sqrt{n})\)。
这个结论知道最好，不知道也问题不大，赛时随一个跑一下也行。
警告：
-
一直考虑正着做，产生了思维定式
-
正难则反啊，反着做发现只需考虑第一次覆盖的数就行了。
-
接下来的贪心也没想到：序列中不应该出现不在 \(LIS\) 中的数（\(a_n\) 除外），否则删掉他，可以使序列长度减少，跨越序列的代价就减少了。
-
然后就是 dp，转移发现上个树状数组优化即可。
时间复杂度：\(O(n\sqrt{n}\log n)\)，空间复杂度：\(O(n\sqrt{n})\)
最后讲一下卡常的点：
-
开 short
-
枚举 \(LIS\) 长度时，如果当前 dp 值为 \(\inf\)，那么就可以 break 了（注意要在 \(LIS\) > 2 时才满足这个性质）
代码
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const short N=1.5e4+10,INF=N*2,M=3e2+10;
short n,a[N];
short f[N][M],g[N][M];
struct BIT1{
short c[N];
void init(){
memset(c,0x7f,sizeof c);
}
void add(short x,short y){
for(;x&&c[x]>y;x^=x&-x)c[x]=y;
}
void get(short x,short &y){
for(;x<=n;x+=x&-x)c[x]<y&&(y=c[x]);
}
}F[M];
struct BIT2{
short c[N];
void init(){
memset(c,-0x7f,sizeof c);
}
void add(short x,short y){
for(;x<=n&&c[x]<y;x+=x&-x)c[x]=y;
}
void get(short x,short &y){
for(;x;x^=x&-x)c[x]>y&&(y=c[x]);
}
}G[M];
struct opts{
short x,y,z;
};
vector<opts>oF[N],oG[N];
short ans=0;
void init(){
memset(f,0x7f,sizeof f),memset(g,-0x7f,sizeof g);
memset(F,0x7f,sizeof F),memset(G,-0x7f,sizeof G);
for(short i=1;i<=n;i++)oF[i].clear(),oG[i].clear();
}
short st;
void ins(short i){
for(short x=st;x+1<M;x++){
if(x>2&&f[i][x]>=INF)break;
F[x+1].add(a[i]-1,f[i][x]);
if(i>x)oF[i-x].push_back({short(x+1),f[i][x],a[i]});
}
for(short x=st;x+1<M;x++){
if(x>2&&g[i][x]<=-INF)break;
G[x+1].add(a[i]+1,g[i][x]);
if(i>x)oG[i-x].push_back({short(x+1),g[i][x],a[i]});
}
}
//bool cmp(opts x,opts y){
// return x.x<y.x;
//}
void trs(short i){
// sort(oF[i].begin(),oF[i].end(),cmp);
// sort(oG[i].begin(),oG[i].end(),cmp);
for(opts x:oF[i]){
G[x.x].add(x.y+1,x.z);
}
for(opts x:oG[i]){
F[x.x].add(x.y-1,x.z);
}
for(short x=st;x<M;x++){
F[x].get(a[i],f[i][x]);
if(x>2&&f[i][x]>=INF)break;
}
for(short x=st;x<M;x++){
G[x].get(a[i],g[i][x]);
if(x>2&&g[i][x]<=-INF)break;
}
}
void solve1(){
st=1;
init();
f[n][1]=g[n][1]=a[n];
for(short i=n-1;i>=1;i--){
ins(i+1);
trs(i);
}
for(short i=M-1;i>=1;i--)for(short j=1;j<=n;j++)
if(f[j][i]<INF||g[j][i]>-INF){
ans=max(ans,i);
return;
}
}
void solve2(){
st=2;
init();
for(short i=n-1;i>=1;i--){
ins(i+1);
f[i][2]=min(f[i][2],a[i]);
g[i][2]=max(g[i][2],a[i]);
trs(i);
}
for(short i=M-2;i>=1;i--)for(short j=1;j<=n;j++)
if(f[j][i+1]<INF||g[j][i+1]>-INF){
ans=max(ans,i);
return;
}
}
void read(short &x){
char c;
for(x=0;!isdigit(c=getchar()););
for(;x=(x<<3)+(x<<1)+(c^48),isdigit(c=getchar()););
}
int main(){
read(n);
for(short i=1;i<=n;i++)read(a[i]);
solve1();
solve2();
cout<<ans;
return 0;
}