UVA 11525 好大好大的排列(线段树)

Posted by Cww97 on 2016-03-10

版权声明:本文为博主原创文章,未经博主允许不得转载。原文所在http://blog.csdn.net/cww97 https://blog.csdn.net/cww97/article/details/50849282
题目在这

题意:求1-k的排列中第n大的序列,题目给出n的计算方法:
n = si(k-1)+s2(k-2)…+sk*0!; 并给你s1~sk

分析:n好大好大,,,,,
n是给的一个一个的阶乘和,想想:k位的排列数是k!
从0!到(k-1)!,,,似乎,对应着什么
每一个s[i]对应全排列的一位数字
(蚊子数学太弱,,,证明什么的,,,额)
不过看到一个一个阶乘还是可以yy出这么一个写法的:
每读入一个s[i],选取剩下的数中第s[i]+1小的,
有点拗口是吧,,,拿样例模拟模拟,就搞出来了

k很大,有5w,如果每次都赤裸裸的找的话,
平方复杂度必然TLE,开个线段树吧,
权值是0或1,1表示没被用过,0表示被用过了
维护区间和。。。。每次取剩下的第s[i]+1个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=140000;
int ans;

struct tree{
int su[N],l[N],r[N],M;

void build(int n){
M=1; while(M<n)M<<=1; M--;
for (int i=M+1;i<=M+n;i++)l[i]=r[i]=i-M,su[i]=1;
for (int i=M+n+1;i<=M*2+1;i++)l[i]=r[i]=i-M,su[i]=0;
for (int i=M;i>=1;i--){
l[i]=l[i<<1],r[i]=r[i<<1^1];
su[i]=su[i<<1]+su[i<<1^1];
}
}

void get(int t,int k,int sum){
if (l[t]==r[t]){
ans=l[t];su[t]=0;return;
}
int mid=(l[t]+r[t])>>1;
if (sum+su[t<<1]>=k)get(t<<1,k,sum);
else get(t<<1^1,k,sum+su[t<<1]);
su[t]=su[t<<1]+su[t<<1^1];
}
}T;

int main(){
int cas;scanf("%d",&cas);
while (cas--){
int n;scanf("%d",&n);
T.build(n);
for (int i=1;i<=n;i++){
int x;scanf("%d",&x);
T.get(1,x+1,0);
printf("%d",ans);
if (i<n)printf(" ");
}
puts("");
}
return 0;
}