此帖结

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+50,M=N<<7;
int a[N],n; 
typedef pair<int,int>pii;
struct SegmentTree{
	int tot;
	int lc[M],rc[M];
	pii val[M];
	void pushup(int u){
		val[u]=max(val[lc[u]],val[rc[u]]);
	}
	int update(int u,int l,int r,int pos,int c){
		int t=++tot;
		lc[t]=lc[u],rc[t]=rc[u],val[t]=val[u];
		if(l==r){
			val[t].first=max(val[t].first,c);
			val[t].second=pos;
			return t;
		}
		int mid=(l+r)>>1;
		if(pos<=mid)lc[t]=update(lc[t],l,mid,pos,c);
		else rc[t]=update(rc[t],mid+1,r,pos,c);
		pushup(t);
		return t;
	}
	pii query(int u,int l,int r,int L,int R){
		if(!u)return {0,0};
		if(L<=l && r<=R)return val[u];
		int mid=(l+r)>>1;
		pii res={0,0};
		if(L<=mid)res=max(res,query(lc[u],l,mid,L,R));
		if(R>mid)res=max(res,query(rc[u],mid+1,r,L,R));
		return res;
	}
	int upd(int rt,int pos,int c){
		return update(rt,0,n,pos,c);
	}
	pii qry(int rt,int l,int r){
		return query(rt,0,n,l,r);
	}
}sgt;
int operator + (pii a,pii b){
	return a.first+b.first;
}
int pre[N],suf[N];
int pr[N],sr[N];
int vis[N];
int r[N],p[N];
int main(){
	freopen("lis.in","r",stdin);
	freopen("lis.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;++i)scanf("%d",&a[i]),r[a[i]]=i;
	pr[0]=sgt.upd(0,0,0);
	for(int i=1;i<=n;++i){
		pii t=sgt.qry(pr[i-1],0,a[i]);
		pre[i]=t.first+1;
		p[i]=r[t.second];
		pr[i]=sgt.upd(pr[i-1],a[i],pre[i]);
	}
	sr[n+1]=sgt.upd(0,0,0);
	for(int i=n;i>=1;--i){
		pii t=sgt.qry(sr[i+1],a[i],n);
		suf[i]=t.first+1;
		sr[i]=sgt.upd(sr[i+1],a[i],suf[i]);
	}
	pii t=sgt.qry(pr[n],0,n);
	int res=t.first;
	int c=t.second;
	while(c){
		vis[c]=1;
		c=p[c];
	}
	for(int i=1;i<n;++i){
		int ans=0;
		ans=max(ans,sgt.qry(pr[i-1],0,a[i])+sgt.qry(sr[i+2],a[i],n)+1);//只选新 a[i+1] 
		ans=max(ans,sgt.qry(pr[i-1],0,a[i+1])+sgt.qry(sr[i+2],a[i+1],n)+1);//只选新 a[i] 
		if(a[i+1]<a[i])ans=max(ans,sgt.qry(pr[i-1],0,a[i+1])+sgt.qry(sr[i+2],a[i],n)+2);//同时选 
		if(!vis[i] && !vis[i+1])ans=max(ans,res);//同时不选，若原先在 LIS 上都不选不优，否则取原 LIS 
		printf("%d ",ans); 
	}
	return 0;
}

$55$pts 总是比答案少 $1$ 为什么？