【题意】给定n，记Perm(x)是所有0,1,2,...,n-1的排列中第x大的排列，对于一个0,1,2,...,n-1的排列p，记p是所有0,1,2,...,n-1的排列中字典序从小到大的第Ord(p)个排列，现在给定两个0,1,2,...,n-1的排列p和q，求Perm((Ord(p)+Ord(q))%(n!)).
【解题方法1】利用康托展开（参见 康托展开 - ACdreamer - 博客频道 - CSDN.NET），由于这里需要动态查询rank和order，需要使用数据结构维护，先用Treap做了一发。
【代码1】
//
//Created by just_sort 2016/10/22
//Copyright (c) 2016 just_sort.All Rights Reserved
//
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
using namespace __gnu_pbds;
typedef long long LL;
#define LL long long
#define maxn 200005
class treap //treap是一颗随机的二叉排序树，可以实现插入，删除，询问前驱、后驱、排名等功能，不支持负数。各功能的时间复杂度为O(logn)
{
struct node //treap的节点定义
{
node* ch[2];
int v, r, s;
int cmp(int x)
{
if (x == v) return -1;
return(x < v ? 0 : 1);
}
};
private:
node* root; //treap的根
void updata(node* o)
{
if (!o) return;
o->s = 1;
if (o->ch[0]) o->s += o->ch[0]->s;
if (o->ch[1]) o->s += o->ch[1]->s;
}
void rateto(node* &o, int d)
{
node* k;
k = o->ch[d ^ 1];
o->ch[d ^ 1] = k->ch[d];
k->ch[d] = o;
updata(o);
updata(k);
o = k;
}
int left(node* o)
{
if (!o) return 0;
if (o->ch[0]) return o->ch[0]->s;
else return 0;
}
void mymemory(node* &o)
{
if (!o) return;
if (o->ch[0]) mymemory(o->ch[0]);
if (o->ch[1]) mymemory(o->ch[1]);
free(o);
o = 0;
}
void add(node* &o, int x)
{
if (!o)
{
o = new node();
o->ch[0] = o->ch[1] = 0;
o->v = x;
o->r = rand()*rand();
o->s = 1;
return;
}
int d = o->cmp(x);
if (d == -1) return;
else
{
add(o->ch[d], x);
updata(o);
if (o->r < o->ch[d]->r) rateto(o, d ^ 1);
}
}
void remove(node* &o, int x)
{
if (!o) return;
int d = o->cmp(x);
if (d == -1)
{
if (!(o->ch[0]))
{
node *k = o->ch[1];
free(o);
o = k;
}
else if (!(o->ch[1]))
{
node *k = o->ch[0];
free(o);
o = k;
}
else
{
int d2 = o->ch[0]->r > o->ch[1]->r ? 1 : 0;
rateto(o, d2);
remove(o->ch[d2], x);
}
}
else remove(o->ch[d], x);
updata(o);
}
bool finded(node* o, int x)
{
if (!o) return 0;
while (o)
{
int d = o->cmp(x);
if (d == -1) return 1;
else o = o->ch[d];
}
return 0;
}
int Kth(node* o, int k)
{
if (!o) return -1;
if (k == left(o) + 1) return o->v;
else
{
if (k <= left(o)) return Kth(o->ch[0], k);
else return Kth(o->ch[1], k - left(o) - 1);
}
}
int Rank(node* o, int x, int n)
{
if (!o) return -1;
int d = o->cmp(x);
if (d == -1) return n + left(o) + 1;
if (d == 0) return Rank(o->ch[0], x, n);
else return Rank(o->ch[1], x, n + left(o) + 1);
}
int Suc(node* &o, int x)
{
if (!o) return -1;
int d = o->cmp(x);
if (d == -1)
{
if (o->ch[1]) return Suc(o->ch[1], x);
else return -1;
}
else
{
int s = Suc(o->ch[d], x);
if (s != -1) return s;
if (s == -1 && o->v > x) return o->v;
else return -1;
}
}
int Pre(node* &o, int x)
{
if (!o) return -1;
int d = o->cmp(x);
if (d == -1)
{
if (o->ch[0]) return Pre(o->ch[0], x);
else return -1;
}
else
{
int s = Pre(o->ch[d], x);
if (s != -1) return s;
if (s == -1 && o->v < x) return o->v;
else return -1;
}
}
//以上为treap的功能实现部分
public:
int size()//返回该treap的内元素的个数
{
if (root) return root->s;
else return 0;
}
void insert(int x)//向treap中插元素x，如果x已经在treap中，则不操作
{
add(root, x);
}
void erase(int x)//删除treap中元素x，如果没有，则不操作
{
remove(root, x);
}
bool find(int x)//返回x是否在treap中
{
return finded(root, x);
}
int kth(int x)//返treap中的排名为x的元素的值，如果x非法，返回-1
{
if (x <= 0 || x > size()) return -1;
return Kth(root, x);
}
int rank(int x)//返回x在treap中的排名，如果x不在treap中，返回-1
{
return Rank(root, x, 0);
}
void clear()//清空treap,释放内存
{
mymemory(root);
}
int suc(int x)//返回treap中比x大的第一元素的值（后驱），如果x大于等于treap中的最大值，返回-1
{
return Suc(root, x);
}
int pre(int x)//返回treap中比x小的第一元素的值（前驱），如果x小于等于treap中的最小值，返回-1
{
return Pre(root, x);
}
treap()//定义初始化；
{
root = 0;
}
};
int a[maxn],b[maxn];
int p[maxn],q[maxn];
int c[maxn];
int main()
{
int n;
scanf("%d",&n);
treap ta,tb;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
ta.insert(a[i]);
}
for(int i=1;i<=n;i++)
{
scanf("%d",&b[i]);
tb.insert(b[i]);
}
for(int i=1;i<=n;i++)
{
p[i]=ta.rank(a[i])-1;
ta.erase(a[i]);
}
for(int i=1;i<=n;i++)
{
q[i]=tb.rank(b[i])-1;
tb.erase(b[i]);
}
memset(c,0,sizeof(c));
for(int i=n;i>=1;i--)
{
c[i]+=q[i]+p[i];
if(c[i]>=n-i+1)
{
c[i]-=n-i+1;
c[i-1]++;
}
}
treap tc;
for(int i=0;i<n;i++) tc.insert(i);
for(int i=1;i<=n;i++)
{
int tmp=tc.kth(c[i]+1);
printf("%d ",tmp);
tc.erase(tmp);
}
printf("\n");
return 0;
}
【代码2 平衡树换成pbds】参见q神。。。
//
//Created by just_sort 2016/10/22
//Copyright (c) 2016 just_sort.All Rights Reserved
//
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
using namespace __gnu_pbds;
typedef long long LL;
const int maxn = 200005;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>order_set;
order_set s;
order_set::iterator it;
int n, in[maxn], cantor[3][maxn];
int main()
{
cin>>n;
for(int i = 0; i < n; i++) cin>>in[i];
s.clear();
for(int i = n - 1; i >= 0; i--)
{
cantor[1][n-i-1] = s.order_of_key(in[i]);
s.insert(in[i]);
}
for(int i = 0; i < n; i++) cin>>in[i];
s.clear();
for(int i = n - 1; i >= 0; i--)
{
cantor[2][n-i-1] = s.order_of_key(in[i]);
s.insert(in[i]);
}
int up = 0;
for(int i = 0; i < n; i++)
{
cantor[0][i] = (cantor[1][i] + cantor[2][i] + up) % (i + 1);
up = (cantor[1][i] + cantor[2][i] + up) / (i + 1);
}
s.clear();
vector<int>ans;
for(int i = 0; i < n; i++) s.insert(i);
for(int i = n - 1; i >= 0; i--)
{
it = s.find_by_order(cantor[0][i]);
ans.push_back(*it);
s.erase(it);
}
for(int i = 0; i < ans.size(); i++)
{
cout<<ans[i]<<" ";
}
}
【代码3】树状数组+2分，复杂度 O(n*logn&logn).
京公网安备 11010502036488号