P6795 题解

题目大意

给定一个 $n$ 阶排列 $a_1\sim a_n$ 的前 $m$ 位，确定整个排列使得值域连续段数最大，给出构造。

数据范围：$n\le 2\times 10^5$。

思路分析

设 $a_1\sim a_m$ 离散化后得到 $b_1\sim b_m$。

考虑分类：

• 若左右端点都在 $[1,m]$：直接线段树或析合树统计即可。
• 若左右端点都在 $(m,n]$：可以证明剩余元素的每个值域连续段都是按顺序填在一起的，即每个都不在 $a_1\sim a_m$ 中的值域区间在序列上一定连续。

否则考虑一个前后缀拼合的形态：$[i,m]+(m,j]$，显然一个必要条件是 $b_i\sim b_m$ 是值域连续段。

考虑取出所有 $b$ 的值域连续段，按 $i$ 大到小排序，设这些区间原本的值域是 $[l_1,r_1]\sim [l_k,r_k]$，第 $i$ 个区间对应的后缀是 $b_{p_i}\sim b_m]$。

不妨设当前区间为 $[l_i,r_i]$，考虑从 $[l_{i-1},r_{i-1}]$ 转移的过程：显然会降序加入 $l_{i-1}-1\sim l_i+1$，升序加入 $r_{i-1}+1\sim r_i-1$。

不妨设在 $a_1\sim a_m$ 中：值为 $x$ 的数的前驱是 $pre(x)$，后继是 $suf(x)$，因此我们考虑 $(pre(l_i),l_i)$ 这个区间的贡献，注意到如果有多个 $l_i$ 相等，那么这个区间可以选一个最优的时刻下放。

考虑在当前时刻下放的贡献 $c_i$：

• 若 $l_i\ne l_{i-1}$ 显然 $c_i=1$。
• 否则考虑左端点从 $p_i$ 移动到 $p_{i-1}$ 的过程，注意到指针扫过的 $(p_i,p_{i-1})$ 这个区间，这些数的值域是 $(r_{i-1},r_i)$，如果这个值域里的数都在 $a_1\sim a_m$ 中，那么 $c_{i}=c_{i-1}+1$。
• 否则显然 $c_i\in\{1,2\}$，考虑什么时候 $c_i=2$，那么我们要求 $[r_{i-1}+1,r_i-1]$ 中不在 $a_1\sim a_m$ 中的元素一定紧接着 $r_{i-1}$，具体可以看代码：维护 $a_1\sim a_m$ 排序后的值域区间，要求 $r_{i-1}$ 是 $r_i$ 所在值域区间的上一个值域区间里的最大值。

最终维护每个段最优的下放贡献以及转移点，容易求出答案和构造方案。

代码呈现

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=2e5+5,inf=1e9;
int n,m;
struct SegmentTree {
	struct Node {
		int add,min,cnt;
	}	tr[MAXN<<2];
	inline int L(int p) { return p<<1; }
	inline int R(int p) { return p<<1|1; }
	inline void psu(int p) {
		tr[p].cnt=0,tr[p].min=std::min(tr[L(p)].min,tr[R(p)].min);
		if(tr[L(p)].min==tr[p].min) tr[p].cnt+=tr[L(p)].cnt;
		if(tr[R(p)].min==tr[p].min) tr[p].cnt+=tr[R(p)].cnt;
	}
	inline void adt(int p,int k) { tr[p].add+=k,tr[p].min+=k; }
	inline void psd(int p) { adt(L(p),tr[p].add),adt(R(p),tr[p].add),tr[p].add=0; }
	inline void bd(int l=1,int r=n,int p=1) {
		tr[p].cnt=r-l+1;
		if(l==r) return ;
		int mid=(l+r)>>1;
		bd(l,mid,L(p)),bd(mid+1,r,R(p));
	}
	inline void add(int ul,int ur,int k,int l=1,int r=n,int p=1) {
		if(ul<=l&&r<=ur) return adt(p,k);
		int mid=(l+r)>>1; psd(p);
		if(ul<=mid) add(ul,ur,k,l,mid,L(p));
		if(mid<ur) add(ul,ur,k,mid+1,r,R(p));
		psu(p);
	}
}	T;
int sn[MAXN],tn,sx[MAXN],tx;
int a[MAXN],b[MAXN],rk[MAXN],id[MAXN],L[MAXN],R[MAXN];
int fl[MAXN],fr[MAXN],gl[MAXN],gr[MAXN];
inline void pl(int x) {
	for(int i=b[x]-1;i>=b[x-1]+1;--i) printf("%d ",i);
}
inline void pr(int x) {
	for(int i=b[x]+1;i<=b[x+1]-1;++i) printf("%d ",i);
}
signed main() {	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i) scanf("%d",&a[i]),b[i]=a[i];
	ll ans=0;
	T.bd(),T.add(1,n,inf);
	for(int i=1;i<=m;++i) {
		T.add(1,i,-1),T.add(i,i,-inf+1);
		while(tn&&a[sn[tn]]>a[i]) T.add(sn[tn-1]+1,sn[tn],a[sn[tn]]),--tn;
		sn[++tn]=i,T.add(sn[tn-1]+1,sn[tn],-a[i]);
		while(tx&&a[sx[tx]]<a[i]) T.add(sx[tx-1]+1,sx[tx],-a[sx[tx]]),--tx;
		sx[++tx]=i,T.add(sx[tx-1]+1,sx[tx],a[i]);
		if(!T.tr[1].min&&i<m) ans+=T.tr[1].cnt;
	}
	sort(b+1,b+m+1),b[m+1]=n+1;
	for(int i=1;i<=m;++i) rk[b[i]]=i;
	for(int i=0;i<=m;++i) ans+=1ll*(b[i+1]-b[i]-1)*(b[i+1]-b[i])/2;
	for(int i=1,c=0;i<=m;++i) {
		if(i==1||b[i]>b[i-1]+1) id[i]=++c,L[c]=R[c]=i;
		else R[c]=i,id[i]=c;
	}
	for(int i=m,l=n+1,r=0,kl=n+1,kr=0,wl=0,wr=0;i;--i) {
		l=min(l,rk[a[i]]),r=max(r,rk[a[i]]);
		if(r-l==m-i) {
			if(l<kl) wl=0;
			else if(id[r]!=id[kr]) wl=(kr==R[id[r]-1]);
			if(r>kr) wr=0;
			else if(id[l]!=id[kl]) wr=(kl==L[id[l]+1]);
			++wl,++wr;
			if(wl>fl[l]) fl[l]=wl,gl[l]=i;
			if(wr>fr[r]) fr[r]=wr,gr[r]=i;
			kl=l,kr=r,++ans;
		}
	}
	for(int i=1;i<=m;++i) ans+=1ll*fl[i]*(b[i]-b[i-1]-1)+1ll*fr[i]*(b[i+1]-b[i]-1);
	printf("%lld\n",ans);
	for(int i=1;i<=m;++i) printf("%d ",a[i]);
	for(int i=m,l=n+1,r=0,kl=n+1,kr=0;i;--i) {
		l=min(l,rk[a[i]]),r=max(r,rk[a[i]]);
		if(r-l==m-i) {
			if(i<m) {
				for(int j=kl-1;j>=l+1;--j) pl(j);
				for(int j=kr+1;j<=r-1;++j) pr(j);
			}
			kl=l,kr=r;
			int zl=(gl[l]==i)?fl[l]:0,zr=(gr[r]==i)?fr[r]:0;
			if(zl>zr) {
				if(zl) pl(l);
				if(zr) pr(r);
			} else {
				if(zr) pr(r);
				if(zl) pl(l);
			}
		}
	}
	puts("");
	return 0;
}