B. Misha and Permutations Summation
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Let’s define the sum of two permutationspandqof numbers0,1,…,(n-1)as permutation, wherePerm(x)is thex-th lexicographically permutation of numbers0,1,…,(n-1)(counting from zero), andOrd(p)is the number of permutationpin the lexicographical order.
For example,Perm(0)=(0,1,…,n-2,n-1),Perm(n!-1)=(n-1,n-2,…,1,0)
Misha has two permutations,pandq. Your task is to find their sum.
Permutationa=(a0,a1,…,an-1)is called to be lexicographically smaller than permutationb=(b0,b1,…,bn-1), if for somekfollowing conditions hold:a0=b0,a1=b1,…,ak-1=bk-1,ak<bk.
Input
The first line contains an integern(1≤n≤200000).
The second line containsndistinct integers from0ton-1, separated by a space, forming permutationp.
The third line containsndistinct integers from0ton-1, separated by spaces, forming permutationq.
Output
Printndistinct integers from0ton-1, forming the sum of the given permutations. Separate the numbers by spaces.
Sample test(s)
input
20 10 1
output
0 1
input
20 11 0
output
1 0
input
31 2 02 1 0
output
1 0 2
Note
Permutations of numbers from 0 to 1 in the lexicographical order:(0,1),(1,0).
In the first sampleOrd(p)=0andOrd(q)=0, so the answer is
.
In the second sampleOrd(p)=0andOrd(q)=1, so the answer is.
Permutations of numbers from 0 to 2 in the lexicographical order:(0,1,2),(0,2,1),(1,0,2),(1,2,0),(2,0,1),(2,1,0).
In the third sampleOrd(p)=3andOrd(q)=5, so the answer is.
引用官方题解：
504B – Misha and Permutations Summation
To solve the problem, one need to be able to find the index of given permutation in lexicographical order and permutation by its index. We will store indices in factorial number system. Thus numberxis represented as. You can find the rules of the transformhere.
To make the transform, you may need to use data structures such as binary search tree or binary indexed tree (for maintaining queries of findingk-th number in the set and finding the amount of numbers less than given one).
So, one need to get indices of the permutations, to sum them modulon!and make inverse transform. You can read any accepted solution for better understanding.
Time complexity:.
本题需要会用阶乘来表示一个数字，并能用这种方式来在数与排列之间进行映射（具体见维基)，需要快速查询名次和求第k大。用bit可以在.完成bbst只需要需要#include <bits/stdc++.h>#define foreach(it,v) for(__typeof(v.begin()) it = v.begin(); it != v.end(); ++it)const int maxn = 2e5 + 10;using namespace std;typedef long long ll;int a[maxn],b[maxn],c[maxn],p[maxn],n;int pa[maxn],pb[maxn];void Modify(int x,int val){while(x <= n) {c[x] += val;x += x & -x;}}int Query(int k,int limt = 20){int ans = 0,cnt = 0;for(int i = limt; i >= 0; i–) {ans += (1<<i);if(ans > n||cnt + c[ans]>=k) ans -= (1<<i);else cnt += c[ans];}return ans + 1;}int work(int x,int R){int L = 1;while(L < R) {int mid = (L + R) >> 1;int t = Query(mid);if(x == t)return mid;if(x > t) L = mid;else R = mid;}return L – 1;}int main(int argc, char const *argv[]){ios_base::sync_with_stdio(false);while(cin>>n) {memset(c,0,sizeof (c[0])*(n+1));for(int i = 0; i < n; i++) {cin>>a[i];++a[i];Modify(a[i],1);}int R = n;for(int i = 0; i < n; i++) {pa[i] = work(a[i], R + 1) – 1;R–;Modify(a[i],-1);}memset(c,0,sizeof (c[0])*(n+1));for(int i = 0; i < n; i++) {cin>>b[i];++b[i];Modify(b[i],1);}R = n;for(int i = 0; i < n; i++) {pb[i] = work(b[i], R + 1) – 1;R–;Modify(b[i],-1);}memset(p,0,sizeof(p[0])*(n+1));for(int i = n-1; i >= 0; i–) {p[i] += pa[i] + pb[i];if(i)p[i-1] = p[i] / (n-i);p[i] %= (n-i);}// for(int i = 0; i < n; i++)printf("%d%c", pa[i]," \n"[i+1==n]);// for(int i = 0; i < n; i++)printf("%d%c", pb[i]," \n"[i+1==n]);// for(int i = 0; i < n; i++)printf("%d%c", p[i]," \n"[i+1==n]);memset(c,0,sizeof (c[0])*(n+1));for(int i = 0; i < n; i++) {Modify(i+1,1);}for(int i = 0; i < n; i++) {int t = Query(p[i]+1);printf("%d%c", t-1," \n"[i+1==n]);Modify(t,-1);}}return 0;}
，诚实是人生绝妙的法宝。虽然对人诚实，
