ZYB's Premutation

Memory Limit: 131072/131072 K (Java/Others)

问题描述

ZYBZYB有一个排列PP,但他只记得PP中每个前缀区间的逆序对数,现在他要求你还原这个排列.

(i,j)(i < j)(i,j)(i<j)被称为一对逆序对当且仅当A_i>A_jAi>Aj

输入描述

第一行一个整数TT表示数据组数。

接下来每组数据：

第一行一个正整数NN,描述排列的长度.

第二行NN个正整数A_iAi,描述前缀区间[1,i][1,i]的逆序对数.

数据保证合法.

1 \leq T \leq 51≤T≤5,1 \leq N \leq 500001≤N≤50000

输出描述

TT行每行NN个整数表示答案的排列.

输入样例

输出样例

3 1 2

题解：设f_ifi是第ii个前缀的逆序对数,p_ipi是第ii个位置上的数,则f_i-f_{i-1}fi−fi−1是ii前面比p_ipi大的数的个数.我们考虑倒着做,当我们处理完ii后面的数,第ii个数就是剩下的数中第f_i-f_{i-1}+1fi−fi−1+1大的数,用线段树和树状数组可以轻松地求出当前第kk个是11的位置,复杂度O(N \log N)O(NlogN).

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int maxn = 5e4 + ;

long long arr[maxn],b[maxn];

#define lowbit(x) ((x)&(-x))

struct BinaryIndexTree

{

    int val[maxn],sz;

    void init(int sz){

        this->sz=sz;

        memset(val ,  , sizeof(int)*(sz+));

    }

    void updata(int pos ,int key){

        while(pos<=sz){

            val[pos]+=key;

            pos+=lowbit(pos);

        }

    }

    int prefixsum(int pos){

        int res=;

        while(pos>){

            res+=val[pos];

            pos-=lowbit(pos);

        }

        return res;

    }

    int query(int l,int r){

        return prefixsum(r)-prefixsum(l-);

    }

    //找到第一个大于等于k的位置返回

    //若不存在,返回-1

    int lower_bound(int k){

        if(prefixsum(sz)<k) return -;

        int l =  , r = sz;

        while(l <= r){

            int mid = l + ((r-l)>>);

            if(prefixsum(mid) < k) l = mid + ;

            else r = mid - ;

        }

        return l;

       }

}solver;

int ans[maxn];

int main(int argc,char *argv[]){

    int Case;

    scanf("%d",&Case);

    while(Case--){

        int n;

        scanf("%d",&n);

        solver.init(n);

        for(int i =  ; i <= n ; ++ i) scanf("%I64d",arr+i);

        for(int i =  ; i <= n ; ++ i) b[i] = arr[i] - arr[i-];

        for(int i =  ; i <= n ; ++ i) solver.updata(i , );

        for(int i = n ; i >=  ; -- i){

            long long rank = i - b[i];

            int t = solver.lower_bound(rank);

            ans[i] = t;

            solver.updata(t,-);

        }

        printf("%d",ans[]);

        for(int i =  ; i <= n ; ++ i) printf(" %d",ans[i]);

        printf("\n");

    }

    return ;

}

代码

二分法

#include <iostream>

#include <cstdio>

#include <cmath>

#include <cstring>

#include <algorithm>

using namespace std;

const int N = 1e5+, M = , mod = 1e9+, inf = 0x3f3f3f3f;

typedef long long ll;

//不同为1，相同为0

int n;

struct BIT {

    int tree[N] ;

    int lowbit(int x) {

        return x&(-x);

    }

    void add(int x, int add, int n) {

        for (; x <= n; x += lowbit(x)) {

            tree[x] += add;

        }

    }

    int sum(int x) {

        int s = ;

        for (; x > ; x -= lowbit(x)) {

            s += tree[x];

        }

        return s;

    }

    void clears() {

        memset(tree, , sizeof tree);

    }

}Bit;

int cal(int x) {

    int l = , r = n, ret = -;

    while(l<=r) {

        int mid = (l+r)>>;

        int G = Bit.sum(n) - Bit.sum(mid-);

        if(G>=x) l = mid+, ret = mid;

        else r = mid-;

    }

    return ret;

}

int main() {

    int T,b[N],a[N],ans[N];

    scanf("%d",&T);

    while(T--) {

        scanf("%d",&n);

        for(int i=;i<=n;i++) scanf("%d",&a[i]),b[i] = a[i] - a[i-];

        Bit.clears();

        for(int i=;i<=n;i++) Bit.add(i,,n);

        int pos = n - b[n];

        ans[n] = pos;

        Bit.add(pos,-,n);

        for(int i = n-;i >= ;i--) {

            pos = cal(b[i]+);

            ans[i] = pos;

            Bit.add(pos,-,n);

        }

        for(int i=;i<n;i++) {

            printf("%d ",ans[i]);

        }

        printf("%d\n",ans[n]);

    }

    return ;

}

巴特西

hdu5592/BestCoder Round #65 树状数组寻找第K大

ZYB's Premutation

最新文章

热门文章