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

**UPD 2021/3/26 感谢 @LiM_817 发现了一些笔误，已修改** 我认为其它题解中 $f$ 数组（也就是“右边有多少空位”之类的表述）的定义多少不太明了或有问题，于是写一个我认为清楚一些的： 首先很容易想到一个（只在 $d_i$ 互不相同时正确） 的贪心，这个贪心的思路以及反例参考其它题解。 正解则是考虑**按位确定**：考虑从 $1$ 到 $n$ 依次确定该点选了哪个值，确定 $i$ 这个位置的值时，我们选取满足以下条件的值： 1. 使得这个东西确定之后，存在一种 $i+1$ 到 $n$ 的分配方案，使得总方案合法。 2. 尽可能大。 容易证明这个过程结束之后取到的就是字典序最大的合法方案。（这个方法对于其它求字典序最大值的方案也适用，是一个非常套路的东西） 那么接下来的思路将会是这样的： - 既然是逐位确定，那我们考虑动态确定，动态维护接下来确定什么合法 - 确定了一个点不仅仅确定了这个值，其实相当于限制了它的子树内的点都 $\geq x$，或者说，这是对之后的尚未确定的值进行限定。 - 我们发现上述限定是充分必要的，于是可以直接维护它作为是否合法的判据。 - 根据限制满足的贪心性质，发现这个东西可以奇妙地使用线段树维护。 ------------ 考虑本题中我们如何判定一个值的选取是否合法。 若我们新确定了某个位置的值，考虑确定了它之后，会怎么影响接下来的点取值的合法性。 考虑限制：一个子树内的所有点要 $\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$ 上的影响是一模一样的。 参考代码： ```cpp #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; } ```