bzoj千题计划324：bzoj5249: [2018多省省队联测]IIIDX（线段树）

https://www.lydsy.com/JudgeOnline/problem.php?id=5249

把树建出来

如果所有的d互不相同，后续遍历即可

现在有的d相同

将d从小到大排序，考虑如何将这n个数填进树里

相当与为x的子树预订d序列中的一段

而且当且这个d填的位置越靠后越好

CTSC试机现场发题解，真爽。。。

#include<cmath>
#include<cstdio>
#include<iostream>
#include<algorithm>using namespace std;#define N 500001int d[N],ans[N];int siz[N];int front[N],nxt[N],to[N],tot;int sum[N<<];void read(int &x)
{
    x=; char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) { x=x*+c-''; c=getchar(); }
}void add(int u,int v)
{
    to[++tot]=v; nxt[tot]=front[u]; front[u]=tot;
    siz[u]+=siz[v];
}void change(int k,int l,int r,int pos,int w)
{
    if(l==r)
    {
        sum[k]+=w;
        return;
    }
    int mid=l+r>>;
    if(pos<=mid) change(k<<,l,mid,pos,w);
    else change(k<<|,mid+,r,pos,w);
    sum[k]=sum[k<<]+sum[k<<|];
}int find(int k,int l,int r,int s)
{
    if(l==r) return l;
    int mid=l+r>>;
    if(s<=sum[k<<|]) return find(k<<|,mid+,r,s);
    return find(k<<,l,mid,s-sum[k<<|]);
}int main()
{
    int n;
    double k;
    read(n); scanf("%lf",&k);
    for(int i=;i<=n;++i) read(d[i]);
    sort(d+,d+n+);
    for(int i=;i<=n;++i) siz[i]=;
    for(int i=n;i;--i) add(i/k,i);
    for(int i=front[];i;i=nxt[i]) change(,,n,to[i],siz[to[i]]);
    int j=,t;
    for(int i=;i<=n;i=j)
{
        while(j<=n && d[i]==d[j]) j++;
        for(int l=j-i;l;--l)
        {
            t=find(,,n,l);
            ans[t]=d[i];
            change(,,n,t,-siz[t]);
            for(int h=front[t];h;h=nxt[h]) change(,,n,to[h],siz[to[h]]);
        }
    }
    for(int i=;i<=n;++i) printf("%d ",ans[i]);
    return ;
}