BZOJ 2789: [Poi2012]Letters( BIT )

直接求逆序对就行了...时间复杂度O(nlogn)

-------------------------------------------------------------------------

#include<bits/stdc++.h>

using namespace std;

#define idx(c) ((c) - 'A')

#define lowbit(x) ((x) & -(x))

const int charset = 26;

const int maxn = 1000009;

stack<int> let[charset];

int N;

long long ans = 0;

char A[maxn], B[maxn];

struct BIT {

int b[maxn];

BIT() {

memset(b, 0, sizeof b);

}

inline void add(int p) {

for(++p; p <= N; p += lowbit(p))

b[p]++;

}

inline int sum(int p) {

int ret = 0;

for(++p; p; p -= lowbit(p))

ret += b[p];

return ret;

}

} bit;

int main() {

cin >> N;

scanf("%s", A); scanf("%s", B);

for(int i = 0; i < N; i++)

let[idx(A[i])].push(i);

for(int i = N - 1; ~i; i--) {

int t = let[idx(B[i])].top(); let[idx(B[i])].pop();

ans += bit.sum(t);

bit.add(t);

}

cout << ans << " ";

return 0;

}

-------------------------------------------------------------------------

2789: [Poi2012]Letters

Time Limit: 20 Sec Memory Limit: 128 MB
Submit: 210 Solved: 144
[Submit][Status][Discuss]

Description

给出两个长度相同且由大写英文字母组成的字符串A、B，保证A和B中每种字母出现的次数相同。

现在每次可以交换A中相邻两个字符，求最少需要交换多少次可以使得A变成B。

Input

第一行一个正整数n (2<=n<=1,000,000)，表示字符串的长度。

第二行和第三行各一个长度为n的字符串，并且只包含大写英文字母。

Output

一个非负整数，表示最少的交换次数。

Sample Input

3
ABC
BCA

Sample Output

HINT

ABC -> BAC -> BCA

Source

鸣谢 oimaster