[??记录]ARC114F Permutation Division
command_block
2021-10-28 19:19:48
**题意** ： 给出排列 $P_{1\sim n}$ 。
A 需要将 $P$ 划分为恰好 $k$ 个连续区间，然后 B 将它们重新排列并拼接，得到排列 $Q$。
A 时希望 $Q$ 的字典序最小，B 希望 $Q$ 的字典序最大，求最终得到的 $Q$。
$n\leq 2\times 10^5$ ，时限$\texttt{2s}$。
------------
B 的策略显然是按照每一段的第一个数从大到小排序。
注意到 $P_1$ 一定是一段的开头，分类讨论。
- $P_1\leq k$
此时 A 分段的开头一定是 $1,2,3,...,k$ ，这可以使得 $Q_1=k$ ,其他方法都会使得 $Q_1>k$ 。
- $P_1>k$
此时其他段的首位都必须 $<P_1$ ，这样才能使得 $Q_1=P_1$ ，显然这是下界。
显然 $Q$ 的字典序要大于 $P$ ，我们可以先考虑最大化 $P,Q$ 的最长公共前缀长度。
二分这个长度 $l$，考虑如何判定。
可以在 $l$ 内切分出 $a$ 段，满足开头是下降子序列（这样就会保持原序），记最后一段的开头是 $x$ ，则需在 $l$ 后面切分出 $k-a$ 段，要满足每段开头均 $<x$ 。
记 $dp_i$ 表示以 $P_i$ 结尾（以 $P_1$ 开头）的最长下降子序列，枚举 $x=P_i$ 判，数 $l$ 后面 $<P_i$ 的元素个数，看看是否 $\geq k-dp_i$ 即可判定。
得到 $l$ 之后，需要最小化之后的排列。
继续考虑上述策略，对于（合法的） $x=P_i$ ，我们在 $l$ 后面的决策显然是找最小的 $k-dp_i$ 个元素作为开头，其中第 $k-dp_i$ 小的就是下一位。
最小化 $k-dp_i$ 的值之后，策略已经确定。
复杂度 $O(n\log n)$。
- 总结：在字典序问题中，对方案的一部分进行最大化，即可确定（强力约束）决策。
```cpp
#include<algorithm>
#include<cstdio>
#define Pr pair<int,int>
#define mp make_pair
#define fir first
#define sec second
#define MaxN 200500
using namespace std;
Pr a[MaxN<<2],wfc;int n,to;
void chg(int l=1,int r=n,int u=1)
{
if (l==r){a[u]=wfc;return ;}
int mid=(l+r)>>1;
if (to<=mid)chg(l,mid,u<<1);
else chg(mid+1,r,u<<1|1);
a[u]=max(a[u<<1],a[u<<1|1]);
}
Pr ret;int wfl;
void qry(int l=1,int r=n,int u=1)
{
if (wfl<=l){ret=max(ret,a[u]);return ;}
int mid=(l+r)>>1;
if (wfl<=mid)qry(l,mid,u<<1);
qry(mid+1,r,u<<1|1);
}
int k,p[MaxN],dp[MaxN],pre[MaxN],o[MaxN];
bool chk(int lim)
{
for (int i=1;i<=n;i++)o[i]=0;
for (int i=lim+1;i<=n;i++)o[p[i]]++;
for (int i=1;i<=n;i++)o[i]+=o[i-1];
for (int i=1;i<=lim;i++)if (dp[i])
if (o[p[i]]>=k-dp[i])return 1;
return 0;
}
int ans[MaxN],tp[MaxN],st[MaxN];
bool e[MaxN];
int main()
{
scanf("%d%d",&n,&k);
for (int i=1;i<=n;i++)
{scanf("%d",&p[i]);tp[p[i]]=i;}
if (p[1]<=k){
for (int i=1;i<=k;i++)ans[i]=i;
}else {
wfc=mp(dp[1]=1,1);to=p[1];chg();
for (int i=2;i<=n;i++){
wfl=p[i];ret=mp(0,0);qry();
if (ret.fir){
dp[i]=ret.fir+1;pre[i]=ret.sec;
wfc=mp(dp[i],i);to=p[i];chg();
}
}
int l=1,r=n,mid;
while(l<r){
mid=(l+r+1)>>1;
if (chk(mid))l=mid;
else r=mid-1;
}
if (l==n){
for (int i=1;i<=n;i++)
printf("%d ",p[i]);puts("");
return 0;
}
int tn=0,tot=0;
for (int i=l+1;i<=n;i++)st[++tn]=p[i];
sort(st+1,st+tn+1);
int j=0;
for (int i=1;i<=l;i++)
if (p[i]>st[k-dp[i]]&&dp[i]>dp[j])j=i;
for (int i=j;i;i=pre[i])ans[++tot]=p[i];
for (int i=1;i<=k-dp[j];i++)ans[++tot]=st[i];
}
sort(ans+1,ans+k+1);
for (int i=1;i<=k;i++)e[tp[ans[i]]]=1;
for (int i=k;i;i--){
int j=tp[ans[i]];e[j]=0;
for (int k=j;k<=n&&!e[k];k++)
{e[k]=1;printf("%d ",p[k]);}
}
return 0;
}
```