NOIP模拟 排列【權值線段樹】

題目大意：

對于一個1到n的排列，若知道每一位的逆序數（第i位a[i]的逆序數就是a[1]~a[i-1]中比a[i]大的數的個數），則能求出原排列。

現在對于排列{a[i]}，給出{p[i]}。p[i]表示a[1]~a[i]的逆序數和。請你求出原排列。（1<=n<=100000）

解題思路：

先求出每個數的逆序數，仍設為p[i]，倒着确定，那對于最後一個未确定的數a[i]來說，它前面有p[i]個比它大的數，是以他就是剩下未确定的中的第i-p[i]小的數，用權值線段樹維護即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#define ll long long
using namespace std;

int getint()
{
    int i=,f=;char c;
    for(c=getchar();(c<'0'||c>'9')&&c!='-';c=getchar());
    if(c=='-')f=-,c=getchar();
    for(;c>='0'&&c<='9';c=getchar())i=(i<<)+(i<<)+c-'0';
    return i*f;
}

ll getll()
{
    ll i=,f=;char c;
    for(c=getchar();(c<'0'||c>'9')&&c!='-';c=getchar());
    if(c=='-')f=-,c=getchar();
    for(;c>='0'&&c<='9';c=getchar())i=i*10+c-'0';
    return i*f;
}

const int N=;
int n,a[N],tr[N<<];
ll p[N];

void build(int k,int l,int r)
{
    if(l==r)
    {
        tr[k]=;
        return;
    }
    int mid=l+r>>;
    build(k<<,l,mid),build(k<<|,mid+,r);
    tr[k]=tr[k<<]+tr[k<<|];
}

int query(int k,int l,int r,int num)
{
    if(l==r)
    {
        tr[k]=;
        return l;
    }
    int mid=l+r>>,res;
    if(num<=tr[k<<])res=query(k<<,l,mid,num);
    else res=query(k<<|,mid+,r,num-tr[k<<]);
    tr[k]=tr[k<<]+tr[k<<|];
    return res;
}

int main()
{
    //freopen("premu.in","r",stdin);
    //freopen("premu.out","w",stdout);
    n=getint();
    for(int i=;i<=n;i++)p[i]=getll();
    for(int i=n;i;i--)p[i]-=p[i-];
    for(int i=;i<=n;i++)p[i]=i-p[i];
    build(,,n);
    for(int i=n;i;i--)
        a[i]=query(,,n,p[i]);
    for(int i=;i<=n;i++)
        cout<<a[i]<<' ';
    return ;
}