专栏文章
UVA11525 Permutation 题解
UVA11525题解参与者 1已保存评论 0
文章操作
快速查看文章及其快照的属性,并进行相关操作。
- 当前评论
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @mipaue8o
- 此快照首次捕获于
- 2025/12/03 08:59 3 个月前
- 此快照最后确认于
- 2025/12/03 08:59 3 个月前
前置知识
解法
题目贴心地帮助我们把排名转化成了康托展开完 Lehmer 码的形式(因排序从 开始标号,也不需要手动减 后更新 ),现在就只需要支持查询动态第 小,可以使用权值线段树上二分来处理。
注意本题评测时未过滤行末空格。
代码
CPP#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;
}
相关推荐
评论
共 0 条评论,欢迎与作者交流。
正在加载评论...