洛谷P4364 [九省聯考2018]IIIDX（線段樹）

傳送門

?

題解看得……很……迷？

因為取完一個數后，它的子樹中只能取權值小于等于它的數。我們先把權值從大到小排序，然后記$a_i$為他左邊（包括自己）所有取完他還能取的數的個數。那么當取完一個點$x$的數之后，我們需要為它子樹中的點預留出權值，這些權值肯定在它的左邊。但我們不知道它子樹中的數會取哪幾個數，所以我們就把$x$及其右邊的數的$a_i$全都減去$x$的子樹大小$size_x$，那么就代表$x$的左邊有這么多位置被占據了。那么某一個點$y$要取值的時候，我們只要在線段樹上找到最左邊的一個點，滿足它右邊（包括自己）所有的$a_i$都大于等于當前子樹的$size$即可，這個在線段樹上二分就可以了

然后要注意，父親給他們預留出了權值，那么在做到兒子的時候把這些預留的空間取出來，也就是把上面的影響消除。父親只給兒子預留了一次空間，所以消除影響也只需要一次就夠了

//minamoto
#include<bits/stdc++.h>
using namespace std;
inline int read(){
    #define num ch-'0'
    char ch;bool flag=0;int res;
    while(!isdigit(ch=getchar()))
    (ch=='-')&&(flag=true);
    for(res=num;isdigit(ch=getchar());res=res*10+num);
    (flag)&&(res=-res);
    #undef num
    return res;
}
const int N=5e5+5;
int mn[N<<2],tag[N<<2];
int n;double k;
int a[N],ans[N],sz[N],fa[N],cnt[N];
inline bool cmp(int a,int b){return a>b;}
#define ls (p<<1)
#define rs (p<<1|1)
inline void upd(int p){mn[p]=min(mn[ls],mn[rs]);}
inline void ppd(int p,int t){mn[p]+=t,tag[p]+=t;}
inline void pd(int p){ppd(ls,tag[p]),ppd(rs,tag[p]),tag[p]=0;}
void build(int p,int l,int r){
    if(l==r) return (void)(mn[p]=l);
    int mid=(l+r)>>1;
    build(ls,l,mid),build(rs,mid+1,r),upd(p);
}
int query(int p,int l,int r,int k){
    if(l==r) return mn[p]>=k?l:l+1;
    int mid=(l+r)>>1;if(tag[p]) pd(p);
    return k<=mn[rs]?query(ls,l,mid,k):query(rs,mid+1,r,k);
}
void update(int p,int l,int r,int ql,int qr,int k){
    if(ql<=l&&qr>=r) return (void)(ppd(p,k));
    int mid=(l+r)>>1;if(tag[p]) pd(p);
    if(ql<=mid) update(ls,l,mid,ql,qr,k);
    if(qr>mid) update(rs,mid+1,r,ql,qr,k);
    upd(p);
}
int main(){
//    freopen("testdata.in","r",stdin);
    n=read();scanf("%lf",&k);
    for(int i=1;i<=n;++i) a[i]=read();
    sort(a+1,a+1+n,cmp);
    for(int i=n-1;i;--i)
    cnt[i]=a[i]==a[i+1]?cnt[i+1]+1:0;
    for(int i=1;i<=n;++i) fa[i]=(int)(i/k),sz[i]=1;
    for(int i=n;i;--i) sz[fa[i]]+=sz[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,sz[fa[i]]-1);
        int x=query(1,1,n,sz[i]);
        x+=cnt[x],++cnt[x],x-=(cnt[x]-1);ans[i]=x;
        update(1,1,n,x,n,-sz[i]);
    }
    for(int i=1;i<=n;++i) printf("%d ",a[ans[i]]);
    return 0;
}

?