UVA11525 Permutation 题解

hzoi_Shadow · 2025-05-14 21:22:50 · 题解

题目传送门

前置知识

康托展开 | 线段树基础

解法

题目贴心地帮助我们把排名转化成了康托展开完 Lehmer 码的形式（因排序从 0 开始标号，也不需要手动减 1 后更新 s_{i}），现在就只需要支持查询动态第 k 小，可以使用权值线段树上二分来处理。

注意本题评测时未过滤行末空格。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define ull unsigned long long
#define sort stable_sort 
#define endl '\n'
struct SMT
{
    struct SegmentTree
    {
        int sum;
    }tree[200010];
    #define lson(rt) (rt<<1)
    #define rson(rt) (rt<<1|1)
    void pushup(int rt)
    {
        tree[rt].sum=tree[lson(rt)].sum+tree[rson(rt)].sum;
    }
    void build(int rt,int l,int r)
    {
        tree[rt].sum=r-l+1;
        if(l==r)  return;
        int mid=(l+r)/2;
        build(lson(rt),l,mid);  build(rson(rt),mid+1,r);
    }
    int query(int rt,int l,int r,int k)
    {
        if(l==r)
        {
            tree[rt].sum=0;
            return l; 
        }
        int mid=(l+r)/2,ans=0;
        if(k<=tree[lson(rt)].sum)  ans=query(lson(rt),l,mid,k);
        else  ans=query(rson(rt),mid+1,r,k-tree[lson(rt)].sum);
        pushup(rt); 
        return ans;
    }
}T;
int main()
{
// #define Isaac
#ifdef Isaac
    freopen("in.in","r",stdin);
    freopen("out.out","w",stdout);
#endif
    int t,n,x,i;
    cin>>t;
    for(;t>=1;t--)
    {
        cin>>n;  T.build(1,1,n);
        for(i=1;i<=n;i++)
        {
            cin>>x;
            cout<<T.query(1,1,n,x+1);
            if(i!=n)  cout<<" ";
        }
        cout<<endl;
    }
    return 0;
}