【UOJ 278】[UTR #2] 题目排列顺序

相关链接

题目传送门：http://uoj.ac/contest/36/problem/278
解题报告：http://jiry-2.blog.uoj.ac/blog/2242

解题报告

这个题目看一眼就觉得搞一个差分约束系统
然后用函数式线段树优化建图
时间复杂度 $ O(nlo{g^2}n)$
感觉可以过的样子！

然后去看题解：

直接排一个序就可以了

不要问我为什么跪在地上

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 100000+9;

int n,vout[N];
pair<int,int> arr[N];

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

int main(){
	n = read();
	for (int i=1;i<=n;i++) {
		arr[i].first = read();
		arr[i].second = -i;
	}
	sort(arr+1, arr+1+n);
	for (int i=1;i<=n;i++)
		vout[-arr[i].second] = i;
	for (int i=1;i<=n;i++)
		printf("%d ",vout[i]);
	return 0;
}