题解 P4364 【[九省联考2018]IIIDX】

· · 题解

UPD 2021/3/26 感谢 @LiM_817 发现了一些笔误，已修改

我认为其它题解中 f 数组（也就是“右边有多少空位”之类的表述）的定义多少不太明了或有问题，于是写一个我认为清楚一些的：

首先很容易想到一个（只在 d_i 互不相同时正确） 的贪心，这个贪心的思路以及反例参考其它题解。

正解则是考虑按位确定：考虑从 1 到 n 依次确定该点选了哪个值，确定 i 这个位置的值时，我们选取满足以下条件的值：

  1. 使得这个东西确定之后，存在一种 i+1 到 n 的分配方案，使得总方案合法。
  2. 尽可能大。

容易证明这个过程结束之后取到的就是字典序最大的合法方案。（这个方法对于其它求字典序最大值的方案也适用，是一个非常套路的东西）

那么接下来的思路将会是这样的：

考虑本题中我们如何判定一个值的选取是否合法。

若我们新确定了某个位置的值，考虑确定了它之后，会怎么影响接下来的点取值的合法性。

考虑限制：一个子树内的所有点要 \geq 其根。

令一个点子树大小为 s_u

那我们知道，若这个位置 u 确定是 x，那么其子树内必须也有 s_u 个 \geq x 的数。

而且这个条件还是充分必要的：若找得到 s_u 个 \geq x 的数，那么一定存在分配方案使得 u 这颗子树合法。

而我们发现我们确定 u 时，其子树内还肯定没有已经确定了的地方，所以它带来的限制就是，要有 s_u 个，\geq x 的数分配给这棵子树。注意之前说明的条件充要，所以这个限制是完备的，或者说，等价于原条件的。

所以我们引入的限制就形如：需要拿走 a_i 个 \geq b_i 的数。

但是我们发现，这个条件其实需要在确定 u 的直接孩子的时候进行去除。

也就是说，每当我们发现一个节点的父亲有着上述限制，须将其删除，并且换成一个 “需要拿走一个 d_i”——因为父亲的值已经确定，所以我们需要把这个值去掉一个。 （刚开始就去除没有任何问题，因为孩子是一个连续区间，所以这个条件在开始被满足就一定一直被满足）

而直观上来讲，我们干的事情其实是：把整棵子树的限制，分成根的限制和这颗子树挂在根上每棵子树的限制。

所以我们还需要支持限制的 删除操作，以及形如 需要拿走一个 =b_i 的数 的操作

限制说完了，怎么判断哪些值满足限制？若我们现在想给 u 这个点分配值：

我们发现，我们只需要找到最大的值 p，使得存在满足条件的一种拿去方案，使得还剩下 s_u 个 \geq p 的数。

考虑令 f_i 代表只考虑 b_j\geq i 的限制，还剩下多少个 \geq i 的数。考虑 \min_{i\leq k} f_i ，我们发现这代表最多还剩下几个 \geq k 的数。

原因是因为为了让剩下的 \geq k 的更多，自然是从 b_j 从大到小考虑每个限制，然后每次都拿最小的，然后其实类似一个不断对于剩下的数压栈弹栈的过程，考虑限制的时候，先压进来加入新来的数，然后每次选最小的弹掉，自然地，栈的大小的最小值就是答案。而栈的大小就是 f_i，若看不懂可以随便选一组限制手动模拟一下。

那么我们发现我们已经会求这个”最大的合法值了“：考虑使用线段树维护 f，一个限制就相当于 [1,b_i] 的值 -a_i，然后找到最大的符合限制的值就是找到最靠右的，前缀 \min\geq s_u 的位置，这个可以通过线段树二分实现。

而最后剩下的一个操作，需要拿走一个 =b_i 的数 ，对应在 f 数组上是 [1,b_i] 的值 -1，也可以维护。

而 f_i 的初始值就是 d 中 \geq i 的数的个数。

其实这个操作和另一个修改操作的形式一模一样，但一个是 \geq b_i，一个是 =b_i，其实这个的道理在于根据上面的贪心论述，我们每次都是拿尽可能小的，而 =b_i 的限制存在的前提是一定能取到一个 =b_i 的（因为需要合法），所以 =b_i 的限制与 \geq 其实一样，所以二者体现在 f 上的影响是一模一样的。

参考代码：

#include<bits/stdc++.h>
using namespace std;
//dengyaotriangle!

const int maxn=500005;

int n,m;double k;
int val[maxn],sval[maxn],cnt[maxn];

struct node{
    int tg,mi;
    node* c[2];
}pool[maxn<<1];int ps;

void pu(node* rt){
    rt->mi=min(rt->c[0]->mi,rt->c[1]->mi);
}
void pd(node* rt){
    rt->mi+=rt->tg;
    if(rt->c[0]){
        rt->c[0]->tg+=rt->tg;
        rt->c[1]->tg+=rt->tg;
    }
    rt->tg=0;

}
node* bt(int l,int r){
    node* nw=pool+ps++;
    if(l==r){
        nw->mi=cnt[l];
    }else{
        nw->c[0]=bt(l,(l+r)>>1);nw->c[1]=bt(((l+r)>>1)+1,r);
        pu(nw);
    }
    return nw;
}

void chg(node* rt,int cl,int cr,int l,int r,int d){
    int cm=(cl+cr)>>1;
    pd(rt);
    if(l==cl&&r==cr)rt->tg+=d,pd(rt);
    else if(r<=cm)chg(rt->c[0],cl,cm,l,r,d),pd(rt->c[1]),pu(rt);
    else if(l>cm)chg(rt->c[1],cm+1,cr,l,r,d),pd(rt->c[0]),pu(rt);
    else chg(rt->c[0],cl,cm,l,cm,d),chg(rt->c[1],cm+1,cr,cm+1,r,d),pu(rt);
}

int find(node* rt,int cl,int cr,int s){
    int cm=(cl+cr)>>1;
    pd(rt);
    if(cl==cr){return cl-1;}
    else{
        pd(rt->c[0]);int w=rt->c[0]->mi;
        if(w<s)return find(rt->c[0],cl,cm,s);
        else return find(rt->c[1],cm+1,cr,s);
    }
}

int ans[maxn];
int sz[maxn];
bool vis[maxn];

int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>val[i];
    sort(val+1,val+1+n);
    for(int i=1;i<=n;i++)sval[i]=val[i];
    m=unique(sval+1,sval+1+n)-sval;
    for(int i=1;i<m;i++)cnt[i]=upper_bound(val+1,val+1+n,sval[i])-lower_bound(val+1,val+1+n,sval[i]);
    for(int i=m-1;i>=1;i--)cnt[i]+=cnt[i+1];
    node* rt=bt(1,m);
    for(int i=n;i>=1;i--){
        sz[i]++;
        sz[(int)floor(i/k)]+=sz[i];
    }
    vis[0]=1;
    for(int i=1;i<=n;i++){
        int fa=(int)floor(i/k);
        if(!vis[fa]){
            vis[fa]=1;
            chg(rt,1,m,1,ans[fa],sz[fa]-1);
        }
        int v=find(rt,1,m,sz[i]);
        ans[i]=v;
        chg(rt,1,m,1,v,-sz[i]);
    }
    for(int i=1;i<=n;i++)cout<<sval[ans[i]]<<' ';
    return 0;
}