command_block 的博客

command_block 的博客

[??记录]ARC114F Permutation Division

posted on 2021-10-28 19:19:48 | under 记录 |

题意 : 给出排列 $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)$。

  • 总结:在字典序问题中,对方案的一部分进行最大化,即可确定(强力约束)决策。
#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;
}