首页 > 代码库 > CF501D Misha and Permutations Summation(康托展开)
CF501D Misha and Permutations Summation(康托展开)
以前写康托展开都是直接O(n^2),碰到了一定要nlogn的,存个代码。
#pragma warning(disable:4996)#include <iostream>#include <cstring>#include <string>#include <vector>#include <cstdio>#include <cmath>#include <algorithm>using namespace std;#define maxn 210000int bit[maxn];int n;void upd(int i){ while (i <= n){ bit[i] += 1; i += i&(-i); }}void dec(int i){ while (i <= n){ bit[i] -= 1; i += i&(-i); }}int cal(int i){ int ret = 0; while (i > 0){ ret += bit[i]; i -= i&(-i); } return ret;}int solve(int x){ int l = 1, r = n+1; while (l < r) { int mid = (l + r) >> 1; int tx = cal(mid); if (tx < x) l = mid + 1; else r = mid; } return l;}int a[maxn];int b[maxn];int c[maxn];int va[maxn];int vb[maxn];int vc[maxn];int main(){ while (cin >> n) { for (int i = 0; i < n; ++i){ scanf("%d", a + i); a[i]++; } for (int i = 0; i < n; ++i){ scanf("%d", b + i); b[i]++; } memset(bit, 0, sizeof(bit)); for (int i = n - 1; i >= 0; --i){ va[i] = cal(a[i]); upd(a[i]); } memset(bit, 0, sizeof(bit)); for (int i = n - 1; i >= 0; --i){ vb[i] = cal(b[i]); upd(b[i]); } reverse(va, va + n); reverse(vb, vb + n); memset(vc, 0, sizeof(vc)); int carry = 0; for (int i = 1; i < n; ++i){ vc[i] = (carry + va[i] + vb[i]) % (i + 1); carry = (carry + va[i] + vb[i]) / (i + 1); } reverse(vc, vc + n); memset(bit, 0, sizeof(bit)); for (int i = 1; i <= n; ++i){ upd(i); } for (int i = 0; i < n; ++i){ c[i] = solve(vc[i]+1); dec(c[i]); } for (int i = 0; i < n; ++i){ if (i) printf(" "); printf("%d", c[i]-1); } puts(""); } return 0;}
CF501D Misha and Permutations Summation(康托展开)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。