FZU2018级算法第二次作业 2.10 逆序数（权值线段树）

题目：

　　Nk 最近喜欢上了研究逆序数，给出一个由 1…n 组成的数列 a1,a2,a3…an，

　　a1的逆序数就是在 a2…an 中，比 a1 小的数的数量，而 a2 的逆序数就是 a3….an 中比 a2 小的数的数量，以此类推。

　　例如，数列 5,3,4,2,1 的逆序数序列就是 4,2,2,1,0.

　　那么，如果给出一个数列的逆序数序列，你能不能还原得到他的原数列？

　　★数据输入

　　每个测试数据是一个正整数 n。代表数列长度（1<=n<=500）,并且原数列中的值的范围是[1,n]。

　　然后输入 n 个正整数 ai（0<=ai<n）

　　★数据输出

　　输出原始数列，两个数字间中间用空格隔开。

输入示例	输出示例
5 4 2 2 1 0	5 3 4 2 1

　　分析下问题，不难发现，第一个数字填入时，除了自己以外的所有数字都在它的后面，因此第一个数字为4。我们可以将1-n所有数字作为一个集合，当第i个数后有ai个比他小的数时，集合中第ai+1大的数就是第i个数字，随后将这个数字从集合中删除。由于n数值过小（虽然线段树不交但是也不至于小到只有500），可以使用链表来完成，也可以使用set进行维护，复杂度均为$O(n^{2})$，当然，set维护写起来比较方便，建议用set维护。这里分享$O(nlogn)$做法，使用权值线段树。

先贴上set代码

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef long double ld;

typedef unsigned long long ull;

typedef pair <int,int> pii;

#define rep(i,x,y) for(int i=x;i<y;i++)

#define rept(i,x,y) for(int i=x;i<=y;i++)

#define per(i,x,y) for(int i=x;i>=y;i--)

#define pb push_back

#define fi first

#define se second

#define mes(a,b) memset(a,b,sizeof a)

const int inf=0x3f3f3f3f;

set<int> s;

set<int> ::iterator pos;

int main()

{

    ios::sync_with_stdio(false);

    cin.tie();

    int n;

    cin>>n;

    rept(i,,n)

        s.insert(i);

    rept(i,,n)

    {

        if(i-) cout<<" ";

        int x;

        cin>>x;

        pos=s.begin();

        for(int i=;i<x;i++,pos++);

        cout<<*pos;

        s.erase(pos);

    }

    cout<<"\n";

    return ;

}

　　对于1-n所有数，建成线段树，每个点标记第i个数为数组中第几大，对于线段树维护区间最大值，每输入一个ai，对于线段数找出大于ai的第一个点，即左区间有大于ai的找左区间，左区间没有则查询右区间。假设数组中第i个数为bi，将线段树中bi的值赋值为0，然后将$[bi+1,n]$区间的每个元素减1即可。

贴上线段树AC代码

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef long double ld;

typedef unsigned long long ull;

typedef pair <int,int> pii;

#define rep(i,x,y) for(int i=x;i<y;i++)

#define rept(i,x,y) for(int i=x;i<=y;i++)

#define pb push_back

#define fi first

#define se second

#define mes(a,b) memset(a,b,sizeof a)

const int maxn=;

ll arrcy[];

class Tree//线段树

{

    public:

        int l,r;

        ll plus,val;

        Tree()

        {

            l=r=val=plus=;

        }

}tree[maxn<<];

void build(int id,int l,int r);

void add(int id,int l,int r,ll num);

void push_down(int id);

int find(int id,int num);

int main()

{

    int n,x,ans;

    cin>>n;

    build(,,n);

    rep(i,,n)

    {

        cin>>x;

        ans=find(,x);

        add(,ans+,n,-);

        add(,ans,ans,-n);

        cout<<ans<<" ";

    }

    return ;

}

void build(int id,int l,int r)

{

    tree[id].l=l;

    tree[id].r=r;

    if(l==r)

    {

        tree[id].val=l;

        return ;

    }

    int mid=(l+r)/;

    build(id*,l,mid);

    build(id*+,mid+,r);

    tree[id].val=max(tree[id*].val,tree[id*+].val);

}

void add(int id,int l,int r,ll num)

{

    if(tree[id].l>=l&&tree[id].r<=r)

    {

        tree[id].plus+=num;

        tree[id].val+=num;

        return ;

    }

    if(tree[id].l>r||tree[id].r<l) return ;

    push_down(id);

    if(tree[id*].r>=l) add(id*,l,r,num);

    if(tree[id*+].l<=r) add(id*+,l,r,num);

    tree[id].val=max(tree[id*].val,tree[id*+].val);

}

void push_down(int id)

{

    rept(j,id*,id*+)

    {

        tree[j].val+=tree[id].plus;

        tree[j].plus+=tree[id].plus;

    }

    tree[id].plus=;

}

int find(int id,int num)

{

    if(tree[id].l==tree[id].r) return tree[id].l;

    push_down(id);

    if(tree[id*].val>num) return find(id*,num);

    else return find(id*+,num);

}

巴特西

FZU2018级算法第二次作业 2.10 逆序数（权值线段树）

最新文章

热门文章