- According to Wikipedia: "In mathematics and in particular in combinatorics, the Lehmer code is a particular way to encode each possible permutation of a sequence of n numbers." To be more specific, for a given permutation of items {
- A?1??, A?2??, ?, A?n??
- }, Lehmer code is a sequence of numbers {
- L?1??, L?2??, ?, L?n??
- } such that L?i?? is the total number of items from A?i?? to A?n?? which are Less than A?i??. For example, given {
- 24, 35, 12, 1, 56, 23
- }, the second Lehmer code L?2?? is 3 since from 35 to 23 there are three items, {
- 12, 1, 23
- }, Less than the second item, 35.
- Input Specification:
Each input file contains one test case. For each case, the first line gives a positive integer N (≤). Then N distinct numbers are given in the next line.
- Output Specification:
- For each test case, output in a line the corresponding Lehmer code. The numbers must be separated by exactly one space, and there must be no extra space at the beginning or the end of the line.
- Sample Input:
- 6 24 35 12 1 56 23
- Sample Output:
- 3 3 1 0 1 0
- #include<bits/stdc++.h>
- #include<ext/pb_ds/assoc_container.hpp>
- #include<ext/pb_ds/tree_policy.hpp>
- using namespace __gnu_pbds;
- using namespace std;
- int main()
- {
- // freopen("data.txt","r",stdin);
- int n,x,c1,c2;
- tree<int,null_type,Less<int>,rb_tree_tag,tree_order_statistics_node_update> tr;
- scanf("%d",&n);
- vector<int> v(n);
- for(int i=0;i<n;i++)
- scanf("%d",&v[i]);
- for(int i=n-1;i>-1;i--)
- {
- tr.insert(v[i]);
- v[i]=tr.order_of_key(v[i]);
- }
- printf("%d",v[0]);
- for(int i=1;i<n;++i)
- printf("%d",v[i]);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3412465.html