题目大意
给出(n,k,d_1,...,d_n)((nleq 5 imes 10^5,1<kleq 10^9,dleq 10^9,kin R))。有一个满足 对于每个点(i)它的父亲是(lfloorfrac{i}{d} floor)（若为0则没父亲）的森林，将(d_1,...,d_n)分配给森林中的每个点，设第(i)号点分配的权值为(w_i)，满足(w_i)不超过子树中所有点的点权，且使(w_1)尽量大，(w_1)相同时使(w_2)尽量大……以此类推。
题解
subtask 1/2：(d)互不相同，55pts
先将(d)从大到小排序，把树建出来，设点(i)的字数大小为(siz_i)。
从1号点考虑：(w_1)越大越好，而有(siz_1)个(w)是必须大于等于(w_1)的，那么(w_1)取(d_{siz_1})最好。
考虑完一号点之后，发现一号点子树里的点只能取(d_i,iin[1,siz_1-1])。
就可以对于每个点维护([l_i,r_i])表示当前这个点的子树中的点只能在该区间中取。
每考虑一个点(x)，就令(w_x=d_{l_{fa_x}+siz_x-1})，并将([l_x,r_x])更新为([l_{fa_x},l_{fa_x}+siz_x-2])，将([l_{fa_x},r_{fa_x}])更新为([l_{fa_x}+siz_x,r_{fa_x}])。
subtask 2/2：无特殊限制，45pts
发现上一个subtask的方法的问题在于，当(d)排序后长成“!!!!!@@@@@##”（相同的符号表示相同的数）时，如果 (siz_1=7)，那么分配给1号点的子树的数就是“!!!!!@@”，如果2号点不在1号点的子树中，把“!!@@@@@”给1号点的子树，2号点就有机会分到“!”。
也就是说，这个时候考虑每一个点时，选的位置应满足：1.左边的可用的数的个数大于等于(siz_i)；2.在去重后的序列中尽可能靠左；3.在同色段中尽可能靠右。
这时还有一个小问题：因为选的点在同色段中尽可能靠右，所以它左边可用的数的个数可能会大于(siz_i)，这个时候不好规定它的子树中的点具体取哪个区间（或哪些）数。
但是可以把它转化成一些形如“对于(iin[1,x])，有(siz_p)个(d)已经被取了”的事件，和形如“求还可以取(siz_q)个的、在去重后的序列中最靠左、在同色段中最靠右的位置”的询问。
可以维护(a_j)表示对于(iin[1,j])还有(a_j)个(d_i)没有被取。
对于一个“事件”，(jin[x,n])的部分肯定都有(a_j-=siz_p)。
另一部分之所以难求，是因为不知道具体取了哪(siz_p)个数。这部分可以这样处理：按编号从小到大考虑每个点，这样先考虑的点一定比后考虑的点更需要更大的(d)。这样这部分的(a_j)就变成了“当每个事件都尽可能往后取时，对于(iin[1,j])还有(a_j)个(d_i)没有被取”。记每个事件只处理(jin[x,n])得到的数为(a'_j)，那么就有(a_j=min{a‘_c|cin[j,n]})。
直接维护(a)很麻烦，考虑维护(a')：这样每个查询就变成了求最靠前的不少于(siz_q)后缀最小值，可以在线段树上二分；每个事件就变成了把([x,n])区间减(siz_p)。
还要注意一个小问题：考虑到一个点时，应将它父亲为它父亲的子树留出的（不包括它父亲本身）部分去掉，即将([x,n])加(siz_p-1)。这样也不用担心考虑别的子树时算到这部分，因为点(i)的父亲是(lfloorfrac{i}{d}
floor)，所以同层（即父亲相同）的点是连着考虑的，在考虑到别的子树中的点时已经把这部分又减回去了。
代码
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<iomanip>
#include<iostream>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
#define rep(i,x,y) for(int i=(x);i<=(y);++i)
#define dwn(i,x,y) for(int i=(x);i>=(y);--i)
#define maxn 500007
#define maxm 1000007
#define D double
#define ls (u<<1)
#define rs (u<<1|1)
#define mi (l+r>>1)
using namespace std;
int read()
{
int x=0,f=1;char ch=getchar();while(!isdigit(ch)&&ch!='-')ch=getchar();if(ch=='-')f=-1,ch=getchar();
while(isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();return x*f;
}
void write(int x)
{
if(x==0){putchar('0'),putchar(' ');return;}int f=0;char ch[20];if(x<0)putchar('-'),x=-x;
while(x)ch[++f]=x%10+'0',x/=10;while(f)putchar(ch[f--]);putchar(' ');return;
}
D K;
int n,d[maxn],sz[maxn],now,anc[maxn],ans[maxn];
int cntnd,ed[maxn],used[maxn],tr[maxn<<2],mk[maxn<<2];
void pu(int u){tr[u]=min(tr[ls],tr[rs]);}
void mark(int u,int k){tr[u]+=k,mk[u]+=k;}
void pd(int u){if(mk[u]){mark(ls,mk[u]),mark(rs,mk[u]),mk[u]=0;}}
void build(int u,int l,int r)
{
if(l==r){tr[u]=l;return;}
build(ls,l,mi),build(rs,mi+1,r),pu(u);return;
}
void add(int u,int l,int r,int x,int y,int k)
{
if(x<=l&&r<=y){mark(u,k);return;}
pd(u);
if(x<=mi)add(ls,l,mi,x,y,k);
if(y>mi)add(rs,mi+1,r,x,y,k);
pu(u);return;
}
int ask(int u,int l,int r,int k)
{
if(l==r){if(tr[u]<k)return l+1;return l;}
pd(u);
if(tr[rs]>=k)return ask(ls,l,mi,k);
else return ask(rs,mi+1,r,k);
}
int num(int u,int l,int r,int x)
{
if(x<=l&&r<=x)return tr[u];
pd(u);
if(x<=mi)return num(ls,l,mi,x);
else return num(rs,mi+1,r,x);
}
int main()
{
scanf("%d%lf",&n,&K);
rep(i,1,n)d[i]=read(),anc[i]=(D)i/K;
dwn(i,n,1)sz[i]++,sz[anc[i]]+=sz[i];
sort(d+1,d+n+1);reverse(d+1,d+n+1);int now=0;
dwn(i,n,1)
{
if(i==n||d[i]!=d[i+1])ed[i]=i,used[i]=0;
else ed[i]=ed[i+1];
}
build(1,1,n);
rep(i,1,n)
{
if(anc[i]&&anc[i]!=anc[i-1])add(1,1,n,ans[anc[i]],n,sz[anc[i]]-1);
int pos=ed[ask(1,1,n,sz[i])];used[pos]++,pos-=used[pos]-1;
ans[i]=pos,add(1,1,n,ans[i],n,-sz[i]);
}
rep(i,1,n)write(d[ans[i]]);
return 0;
}
一些感想
上面有一句话是“这时还有一个小问题：因为选的点在同色段中尽可能靠右，所以它左边可用的数的个数可能会大于(siz_i)，这个时候不好规定它的子树中的点具体取哪个区间（或哪些）数。”
然而在做题的时候只想到了上面举的例子和样例，就觉得应该把(i)子树中的数无脑选为可选范围内最大的一段。
于是就用平衡树维护安排给每个点的数，每考虑一个点，就是从它的父亲中先找出第(siz_i)大的数，然后找一个数(d_x)使(d_x)在(fa_i)中，且(fa_i)的平衡树中在区间([第siz_i大的数,d_x])的个数大于(siz_i)，且(d_x)尽可能小。
然后把(fa_i)的平衡树在([第siz_i大的数,d_x])这个区间的数都给(i)的平衡树，注意(d_x)有多个时可能只需要给一部分。
令(w_i=)点(i)平衡树中最大的数，并从平衡树中删掉这个数。
这样并不是正确的，因为当(d)排序后一部分为“!!!!!@@@@@”时，如果(siz_1=6,siz_2=4)，分给1的子树的是“!@@@@@”，分给2的子树的是“!!!!”，那么(w_1=)@,(w_2=)!，但是如果把“!!@@@@”给1号点的子树，“!!!@”给2号点的子树，就能有(w_1=)@,(w_2=)@。
不过先留着代码吧，万一哪天出题用上了？
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<iomanip>
#include<iostream>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
#define rep(i,x,y) for(int i=(x);i<=(y);++i)
#define dwn(i,x,y) for(int i=(x);i>=(y);--i)
#define maxn 500007
#define maxm 1000007
#define D double
#define ls son[u][0]
#define rs son[u][1]
using namespace std;
int read()
{
int x=0,f=1;char ch=getchar();while(!isdigit(ch)&&ch!='-')ch=getchar();if(ch=='-')f=-1,ch=getchar();
while(isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();return x*f;
}
void write(int x)
{
if(x==0){putchar('0'),putchar(' ');return;}int f=0;char ch[20];if(x<0)putchar('-'),x=-x;
while(x)ch[++f]=x%10+'0',x/=10;while(f)putchar(ch[f--]);putchar(' ');return;
}
D K;
int n,d[maxn],sz[maxn],now,anc[maxn];
int son[maxm][2],fa[maxm],cntnd,siz[maxm],key[maxm],num[maxm],rt[maxm];
void pu(int u){if(!u)return;siz[u]=num[u];if(ls)siz[u]+=siz[ls];if(rs)siz[u]+=siz[rs];}
int getso(int u){return son[fa[u]][0]!=u;}
void rot(int u)
{
int fu=fa[u],ffu=fa[fu],l=getso(u),fl=getso(fu),r=l^1,rson=son[u][r];
son[u][r]=fu,son[fu][l]=rson;if(ffu)son[ffu][fl]=u;if(rson)fa[rson]=fu;fa[fu]=u,fa[u]=ffu;
pu(fu),pu(u);
}
void splay(int u,int k,int & root)
{
while(fa[u]!=k){if(fa[fa[u]]!=k)rot(getso(u)^getso(fa[u])?u:fa[u]);rot(u);}
if(!k)root=u;
}
void fnd(int k,int & root)
{
int u=root;
while(k!=key[u]&&son[u][k>key[u]])u=son[u][k>key[u]];
splay(u,0,root);
}
int nxt(int k,int f,int & root)
{
fnd(k,root);int u=root;
if((key[u]<k&&!f)||(key[u]>k&&f))return u;
u=son[u][f];if(!u)return u;
while(son[u][f^1])u=son[u][f^1];
return u;
}
int build(int l,int r)
{
int u=l+r>>1;
if(l<=u-1)ls=build(l,u-1),fa[ls]=u;
if(r>=u+1)rs=build(u+1,r),fa[rs]=u;
pu(u);return u;
}
int getp(int k,int & root)
{
int u=root;
while(son[u][1])u=son[u][1];
splay(u,0,root);
while(1)
{
if(siz[rs]>=k)u=rs;
else if(siz[rs]+num[u]<k)k-=siz[rs]+num[u],u=ls;
else {/*cout<<"p:"<<u<<endl;*/return u;}
}
return -1;
}
int getrt(int k,int & root)
{
int u=getp(k,root),lk=nxt(key[u],0,root),tpk=k;
//cout<<"lk:"<<lk<<endl;
if(lk)splay(lk,0,root),u=son[lk][1];
else u=root;//cout<<u<<endl;
while(1)
{
if(siz[ls]>=k)u=ls;
else if(siz[ls]+num[u]<k)k-=siz[ls]+num[u],u=rs;
else break;
}
splay(u,lk,root);k=tpk;
if(siz[ls]+num[u]==k)
{
if(rs)fa[rs]=lk;if(lk)son[lk][1]=rs;else root=rs;
fa[u]=0,rs=0;
pu(u),pu(lk);
return u;
}
int res=ls;ls=0;
int nu=++cntnd;key[nu]=key[u],num[nu]=k-siz[res],num[u]-=k-siz[res],son[nu][key[res]>key[nu]]=res;if(res)fa[res]=nu;
pu(nu),pu(u);if(lk)pu(lk);
return nu;
}
int del(int & root)
{
int u=root;
while(son[u][0])u=son[u][0];
splay(u,0,root);
if(num[u]==1)root=rs,fa[rs]=0;
else num[u]--,pu(u);
return key[u];
}
int main()
{
scanf("%d%lf",&n,&K);
rep(i,1,n)d[i]=read();
sort(d+1,d+n+1);int now=0;
rep(i,1,n)
{
now++;
if(i==n||d[i]!=d[i+1])cntnd++,key[cntnd]=d[i],num[cntnd]=now,now=0;
}
rt[0]=build(1,cntnd);
rep(i,1,n)anc[i]=(D)i/K;
dwn(i,n,1)sz[i]++,sz[anc[i]]+=sz[i];
rep(i,1,n)
{
rt[i]=getrt(sz[i],rt[anc[i]]);
write(del(rt[i]));
}
return 0;
}