本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-03-09 11:24:53

众所周知，A+B Problem 的题解里充斥着各种奇奇怪怪的做法，那为什么这道题没有呢？于是就有了这篇题解。

1.set大法好

我们都知道，STL 有 sort 和 priority_queue 给我们用，但却很少人想到 set 也是可以排序的。由于有重复元素，所以这里使用 multiset。

#include<bits\/stdc++.h>
using namespace std;
int main() {
	int n,x;
	multiset<int> s;
	cin>>n;
	while(n--) {cin>>x;s.insert(x);}
	for(int t:s) cout<<t<<" ";
	return 0;
}

虽然非常“巧妙”，但是这使用了 STL，违背了题目要求，于是：

2.桶排序

我们都知道，桶排序是非常快的，只需要 $O(N)$ 的时间和 $O(a_i)$ 的空间，然而这题 $a_i$ 最大到了 $10^9$，面对这种情况，最常见的选择就是是离散化（迫真）。于是，我们先对数组离散化一下，再把数组中元素的离散化结果扔到桶里面，最后扫一遍桶中元素即可。

#include<bits\/stdc++.h>
using namespace std;
int n,a[100010],b[100010],cnt=0;
int t[100010];
int main() {
	cin>>n;
	for(int i=1;i<=n;i++) {
		cin>>a[i];
		b[++cnt]=a[i];
	}
	sort(b+1,b+cnt+1);
	cnt=unique(b+1,b+cnt+1)-b-1;
	for(int i=1;i<=n;i++) {
		int tmp=lower_bound(b+1,b+cnt+1,a[i])-b;
		t[tmp]++;
	}
	for(int i=1;i<=cnt;i++)
		while(t[i]--)
			cout<<b[i]<<" ";
	cout<<endl;
	return 0;
}

你可能会问：这不是还是需要 sort 吗？没错，但你还是不能否认桶排序就是快（实际上，这是本篇题解中最快的做法了）。

但是，使用了 sort 确实违背了题目要求，于是：

3.动态开点权值线段树

这题不是显然可以用权值线段树做吗。。。由于数据范围比较大，要么离散化要么动态开点。如果离散化，就需要 sort，这违背了我们的初衷，所以我们使用动态开点。

首先依次加入 $n$ 个数，接下来每次询问排名为 $i$ 的数即可，时间复杂度 $O(nlog(n))$。

#include<bits\/stdc++.h>
using namespace std;
const int inf=1e9;
int n,tot=0,root;
struct tree{int num,l,r,lson,rson;} t[2000010];
#define mid (t[now].l+t[now].r)\/2
int newnode(int l,int r) {
	t[++tot].l=l,t[tot].r=r;
	return tot;
}
void change(int &now,int x,int l=-inf,int r=inf) {
	if(!now) now=newnode(l,r);
	if(l!=r) {
		if(x<=mid) change(t[now].lson,x,l,mid);
		else change(t[now].rson,x,mid+1,r);
	}
	t[now].num++;
}
int search(int now,int k) {
	if(t[now].l==t[now].r) return t[now].l;
	int val=t[t[now].lson].num;
	if(k<=val) return search(t[now].lson,k);
	else return search(t[now].rson,k-val);
}
int main() {
	cin>>n;
	for(int i=1;i<=n;i++) {
		int x;
		cin>>x;
		change(root,x);
	}
	for(int i=1;i<=n;i++)
		cout<<search(root,i)<<" ";
	cout<<endl;
	return 0;
}

这种做法非常完美的满足了题目的要求：不用任何 STL。完结撒花！