专栏文章

UVA11525 Permutation 题解

UVA11525题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性,并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mipaue8o
此快照首次捕获于
2025/12/03 08:59
3 个月前
此快照最后确认于
2025/12/03 08:59
3 个月前
查看原文

前置知识

解法

题目贴心地帮助我们把排名转化成了康托展开完 Lehmer 码的形式(因排序从 00 开始标号,也不需要手动减 11 后更新 sis_{i}),现在就只需要支持查询动态第 kk 小,可以使用权值线段树上二分来处理。
注意本题评测时未过滤行末空格。

代码

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 条评论,欢迎与作者交流。

正在加载评论...