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

· · 题解

https://sakits.com/bzoj5249/

题解

　　显然题意可以抽象成：一棵树，要对树上的每个点标上给定的权值，满足每个点上的权值都\leq子树内点的权值，并使这个棵树编号从小到大的权值字典序最大。

　　首先可以一眼得到一个做法，将权值从大到小排序，把长度为子树大小的一段按子树编号从小到大丢给它们，递归下去得到答案。

　　这种做法在d_i不重复的时候是正确的，那d_i要是有相同的数呢？

　　有可能可以将编号x子树里一个大的权值与编号x+1的子树根的权值替换，使得x的权值依然是能取得的最大数且子树内的数都比x的权值大，同时x+1子树内的点也还能标满\geqx+1权值的权值。

　　那怎么做呢？先把给定权值从大到小排序，线段树上维护每个权值左边（包括本身）还能取的权值的个数C_i。

　　当取好一个点x的权值时，需要给它子树内的点预留取的权值，这些权值显然在x取得权值的左边，但是我们并不知道取的是哪些权值，所以只把x取得的权值右边（包括本身）的C_i减去x子树大小size[x]，每次取一个点y的权值时，只需要在线段树上找到最大权值val满足val所在位置右边（包括本身）的所有C_i\geq size[y]，且val尽可能靠右即可，这个在线段树上二分就能做到。

　　如果一个点有父亲，求它的权值时要把它父亲为子树预留的大小去掉，需要注意的是，每个父亲预留的大小只要去掉一次，写的时候容易忽略这一点，WA了半天T_T。

代码

#include<iostream> 
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath> 
#include<algorithm> 
using namespace std;
const int maxn=500010, inf=1e9;
struct poi{int mn, delta;}tree[maxn<<2];
int n, N;
double k;
int a[maxn], b[maxn], ans[maxn], size[maxn], fa[maxn], cnt[maxn];
inline void read(int &k)
{
    int f=1; k=0; char c=getchar();
    while(c<'0' || c>'9') c=='-'&&(f=-1), c=getchar();
    while(c<='9' && c>='0') k=k*10+c-'0', c=getchar();
    k*=f;
}
inline bool cmp(int a, int b){return a>b;}
inline void addone(int x, int delta){tree[x].delta+=delta; tree[x].mn+=delta;}
inline void up(int x){tree[x].mn=min(tree[x<<1].mn, tree[x<<1|1].mn);}
inline void down(int x)
{
    addone(x<<1, tree[x].delta);
    addone(x<<1|1, tree[x].delta);
    tree[x].delta=0;
}
void build(int x, int l, int r)
{
    if(l==r){tree[x].mn=l; return;}
    int mid=(l+r)>>1;
    build(x<<1, l, mid); build(x<<1|1, mid+1, r);
    up(x);
}
int query(int x, int l, int r, int k)
{
    if(l==r) return (tree[x].mn>=k?l:l+1);
    down(x);
    int mid=(l+r)>>1;
    if(k<=tree[x<<1|1].mn) return query(x<<1, l, mid, k);
    else return query(x<<1|1, mid+1, r, k);
}
void update(int x, int l, int r, int cl, int cr, int delta)
{
    if(cl<=l && r<=cr){tree[x].mn+=delta; tree[x].delta+=delta; return;}
    down(x);
    int mid=(l+r)>>1;
    if(cl<=mid) update(x<<1, l, mid, cl, cr, delta);
    if(cr>mid) update(x<<1|1, mid+1, r, cl, cr, delta);
    up(x);
}
int main()
{
    read(n); scanf("%lf", &k);  
    for(int i=1;i<=n;i++) read(a[i]);
    sort(a+1, a+1+n, cmp);
    for(int i=n-1;i;i--) 
    if(a[i]==a[i+1]) cnt[i]=cnt[i+1]+1; else cnt[i]=0;
    for(int i=1;i<=n;i++) fa[i]=(int)floor(i/k), size[i]=1;
    for(int i=n;i;i--) size[fa[i]]+=size[i];
    build(1, 1, n);
    for(int i=1;i<=n;i++)
    {
        if(fa[i]&&fa[i]!=fa[i-1]) update(1, 1, n, ans[fa[i]], n, size[fa[i]]-1);
        int x=query(1, 1, n, size[i]); 
        x+=cnt[x]; cnt[x]++; x-=(cnt[x]-1); ans[i]=x; 
        update(1, 1, n, x, n, -size[i]);
    }
    for(int i=1;i<=n;i++) printf("%d ", a[ans[i]]);
}