题解 P4364 【[九省联考2018]IIIDX】
StudyingFather
2020-08-05 19:05:58
题意很简单，给出一个多叉堆，求一种赋值方案，使得其在满足小根堆性质的情况下，编号靠前的点值尽量大。
## Part 1 贪心
先考虑一种贪心做法。
我们先将原序列从大到小排序。容易发现一个子树内的数一定对应序列的一个连续区间。
为了达到靠前的数尽可能大的目的，我们递归到点 $u$ 时，优先将靠前的区间分配给编号较小的子树，而该子树的根节点则取得该子区间右端点的数（小根堆性质）。
**在 $d_i$ 互不相同的时候**，该做法正确性较为显然。
期望得分：$55$ pts（实际可以拿到 $60$ pts）。
## Part 2 贪心·改
上面的做法只能保证 $d_i$ 互不相同时的正确性，当存在相同的 $d_i$ 时会发生什么？
为了方便描述，我们设 $u$ 的某个兄弟节点为 $x$，$u$ 的某个儿子节点为 $v$。
之前的贪心做法，可能会出现 $d_v>d_x=d_u$ 的情况，在这种情况下，如果将 $x$ 和 $v$ 的值互换，可能会在保证堆性质的前提下，让编号较小的点取得更大值。
因此我们需要稍微改良一下原来的做法。
仍然将原序列从大到小排序。不过与之前不同的是，我们这次按层来遍历。
设 $f_i$ 表示当前数左边还能取多少个数。对于 $u$ 点，因为要满足小根堆性质，需要满足 $f_i \geq siz_u$。
因为序列已经排序，因此 $f_i$ 单调不下降，从而考虑二分查找找出满足 $f_i \geq siz_u$ 的最靠左的 $i$。
这里有一个细节，因为存在 $d_i$ 相等的情况，因此这个最靠左的数字右边，可能还存在与之相等的数字。这里我们选择这一连续段中，最靠右的数字，从而解决了旧贪心的弊端。
考虑用线段树维护这一过程。
剩下的就和 Part 1 的做法差不多了。
```cpp
// Problem: P4364 [九省联考2018]IIIDX
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4364
// Memory Limit: 500 MB
// Time Limit: 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
struct seg
{
int minf,tag;
}s[2000005];
int n;
double k;
int d[500005];
int vis[500005],cnt[500005],fa[500005],siz[500005],res[500005];
vector<int> e[500005];
bool cmp(int x,int y)
{
return x>y;
}
void dfs(int u)
{
siz[u]=1;
for(auto v:e[u])
dfs(v),siz[u]+=siz[v];
}
void pushup(int root)
{
s[root].minf=min(s[root<<1].minf,s[root<<1|1].minf);
}
void pushdown(int root)
{
s[root<<1].minf+=s[root].tag,s[root<<1].tag+=s[root].tag;
s[root<<1|1].minf+=s[root].tag,s[root<<1|1].tag+=s[root].tag;
s[root].tag=0;
}
void build(int root,int l,int r)
{
if(l==r)
{
s[root].minf=l;
return;
}
int mid=(l+r)>>1;
build(root<<1,l,mid);
build(root<<1|1,mid+1,r);
pushup(root);
}
void update(int root,int cl,int cr,int l,int r,int x)
{
if(r<cl||cr<l)return;
if(l<=cl&&cr<=r)
{
s[root].minf+=x;
s[root].tag+=x;
return;
}
pushdown(root);
int mid=(cl+cr)>>1;
update(root<<1,cl,mid,l,r,x);
update(root<<1|1,mid+1,cr,l,r,x);
pushup(root);
}
int query(int root,int l,int r,int x)
{
if(l==r)
return s[root].minf>=x?l:l+1;
pushdown(root);
int mid=(l+r)>>1;
if(s[root<<1|1].minf<x)
return query(root<<1|1,mid+1,r,x);
else
return query(root<<1,l,mid,x);
}
int main()
{
ios::sync_with_stdio(false);
cin>>n>>k;
for(int i=1;i<=n;i++)
cin>>d[i];
sort(d+1,d+n+1,cmp);
for(int i=n-1;i;i--)
if(d[i]==d[i+1])cnt[i]=cnt[i+1]+1;
for(int i=1;i<=n;i++)
{
fa[i]=i/k;
e[fa[i]].push_back(i);
}
dfs(0);
build(1,1,n);
for(int i=1;i<=n;i++)
{
if(fa[i]&&!vis[fa[i]])
{
vis[fa[i]]=1;
update(1,1,n,res[fa[i]],n,siz[fa[i]]-1);
}
int pos=query(1,1,n,siz[i]);
pos+=cnt[pos];
cnt[pos]++;
res[i]=pos;
update(1,1,n,res[i],n,-siz[i]);
}
for(int i=1;i<=n;i++)
cout<<d[res[i]]<<' ';
return 0;
}
```