hdu5592 倒序求排列+权值线段树

hdu5592 倒序求排列+权值线段树
强烈推介IDEA2021.1.3破解激活,IntelliJ IDEA 注册码,2021.1.3IDEA 激活码  

大家好,我是架构君,一个会写代码吟诗的架构师。今天说一说hdu5592 倒序求排列+权值线段树,希望能够帮助大家进步!!!

这种题为什么要用到主席树啊、、8说了,直接上代码

/*
1-n的排列,给定所有前缀的逆序对数量,要求恢复排列 
首先能确定最后一个数是什么,然后倒序确定即可 
开线段树找空位:如果Ai-Ai-1=k,说明pi前面有k个数比它要大,,即有i-k-1个数比它小,
那么pi排在第i-k位,线段树查询第i-k个空位,然后把这个空位填上即可 
*/
#include<bits/stdc++.h>
using namespace std;
#define maxn 50005
int n,a[maxn],ans[maxn];

#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
int sum[maxn<<2];
void build(int l,int r,int rt){
    if(l==r){sum[rt]=1;return;}
    int m=l+r>>1;
    build(lson);build(rson);
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void update(int l,int r,int rt,int pos){
    if(l==r){sum[rt]--;return;}
    int m=l+r>>1;
    if(pos<=m)update(lson,pos);
    else update(rson,pos);
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
int query(int l,int r,int rt,int k){
    if(l==r)return l;
    int m=l+r>>1;
    if(k<=sum[rt<<1])return query(lson,k);
    else return query(rson,k-sum[rt<<1]);
}

int main(){
    int T;
    cin>>T;    
    while(T--){
        cin>>n;
        for(int i=1;i<=n;i++)cin>>a[i];
        build(1,n,1);
        for(int i=n;i>=1;i--){
            int k=a[i]-a[i-1];
            ans[i]=query(1,n,1,i-k);
            update(1,n,1,ans[i]);
        } 
        for(int i=1;i<n;i++)cout<<ans[i]<<" ";
        cout<<ans[n]<<endl;
    }
} 

 

转载于:https://www.cnblogs.com/zsben991126/p/10749071.html

本文来源weixin_30595035,由架构君转载发布,观点不代表Java架构师必看的立场,转载请标明来源出处:https://javajgs.com/archives/29882

发表评论