Studying Father's luogu blog

Focus on interest!

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

题意很简单,给出一个多叉堆,求一种赋值方案,使得其在满足小根堆性质的情况下,编号靠前的点值尽量大。

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 的做法差不多了。

// 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;
}

2020-08-05 19:05:58 in 题解