题解看得……很……迷？
因为取完一个数后，它的子树中只能取权值小于等于它的数。我们先把权值从大到小排序，然后记$a_i$为他左边（包括自己）所有取完他还能取的数的个数。那么当取完一个点$x$的数之后，我们需要为它子树中的点预留出权值，这些权值肯定在它的左边。但我们不知道它子树中的数会取哪几个数，所以我们就把$x$及其右边的数的$a_i$全都减去$x$的子树大小$size_x$，那么就代表$x$的左边有这么多位置被占据了。那么某一个点$y$要取值的时候，我们只要在线段树上找到最左边的一个点，满足它右边（包括自己）所有的$a_i$都大于等于当前子树的$size$即可，这个在线段树上二分就可以了
然后要注意，父亲给他们预留出了权值，那么在做到儿子的时候把这些预留的空间取出来，也就是把上面的影响消除。父亲只给儿子预留了一次空间，所以消除影响也只需要一次就够了
1 //minamoto 2 #include<bits/stdc++.h> 3 using namespace std; 4 inline int read(){ 5 #define num ch-‘0‘ 6 char ch;bool flag=0;int res; 7 while(!isdigit(ch=getchar())) 8 (ch==‘-‘)&&(flag=true); 9 for(res=num;isdigit(ch=getchar());res=res*10+num); 10 (flag)&&(res=-res); 11 #undef num 12 return res; 13 } 14 const int N=5e5+5; 15 int mn[N<<2],tag[N<<2]; 16 int n;double k; 17 int a[N],ans[N],sz[N],fa[N],cnt[N]; 18 inline bool cmp(int a,int b){return a>b;} 19 #define ls (p<<1) 20 #define rs (p<<1|1) 21 inline void upd(int p){mn[p]=min(mn[ls],mn[rs]);} 22 inline void ppd(int p,int t){mn[p]+=t,tag[p]+=t;} 23 inline void pd(int p){ppd(ls,tag[p]),ppd(rs,tag[p]),tag[p]=0;} 24 void build(int p,int l,int r){ 25 if(l==r) return (void)(mn[p]=l); 26 int mid=(l+r)>>1; 27 build(ls,l,mid),build(rs,mid+1,r),upd(p); 28 } 29 int query(int p,int l,int r,int k){ 30 if(l==r) return mn[p]>=k?l:l+1; 31 int mid=(l+r)>>1;if(tag[p]) pd(p); 32 return k<=mn[rs]?query(ls,l,mid,k):query(rs,mid+1,r,k); 33 } 34 void update(int p,int l,int r,int ql,int qr,int k){ 35 if(ql<=l&&qr>=r) return (void)(ppd(p,k)); 36 int mid=(l+r)>>1;if(tag[p]) pd(p); 37 if(ql<=mid) update(ls,l,mid,ql,qr,k); 38 if(qr>mid) update(rs,mid+1,r,ql,qr,k); 39 upd(p); 40 } 41 int main(){ 42 // freopen("testdata.in","r",stdin); 43 n=read();scanf("%lf",&k); 44 for(int i=1;i<=n;++i) a[i]=read(); 45 sort(a+1,a+1+n,cmp); 46 for(int i=n-1;i;--i) 47 cnt[i]=a[i]==a[i+1]?cnt[i+1]+1:0; 48 for(int i=1;i<=n;++i) fa[i]=(int)(i/k),sz[i]=1; 49 for(int i=n;i;--i) sz[fa[i]]+=sz[i]; 50 build(1,1,n); 51 for(int i=1;i<=n;++i){ 52 if(fa[i]&&fa[i]!=fa[i-1]) update(1,1,n,ans[fa[i]],n,sz[fa[i]]-1); 53 int x=query(1,1,n,sz[i]); 54 x+=cnt[x],++cnt[x],x-=(cnt[x]-1);ans[i]=x; 55 update(1,1,n,x,n,-sz[i]); 56 } 57 for(int i=1;i<=n;++i) printf("%d ",a[ans[i]]); 58 return 0; 59 }
原文：https://www.cnblogs.com/bztMinamoto/p/9807441.html