洛谷 P3531 [POI2012]LIT-Letters（逆序对）

传送门

解题思路

按照字符在a中出现的位置映射到b字符串中。
求逆序对数即为答案。

AC代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iomanip>
#include<vector>
#include<ctime>
#include<set>
#include<queue>
#include<stack>
#include<algorithm>
using namespace std;
template<class T>inline void read(T &x)
{
    x=0;register char c=getchar();register bool f=0;
    while(!isdigit(c))f^=c=='-',c=getchar();
    while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
    if(f)x=-x;
}
template<class T>inline void print(T x)
{
    if(x<0)putchar('-'),x=-x;
    if(x>9)print(x/10);
    putchar('0'+x%10);
}
vector<int> v[205];
const int maxn=1e6+5;
int n,d[maxn],cnt[maxn],a[maxn];
long long ans;
string s1,s2;
inline int lowbit(int x){
	return x&(-x);
}
void update(int x){
	for(int i=x;i<=n;i+=lowbit(i)){
		d[i]++;
	}
}
int query(int x){
	int res=0;
	for(int i=x;i>=1;i-=lowbit(i)){
		res+=d[i];
	}
	return res;
}
int main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	ios::sync_with_stdio(false);
	cin>>n;
	cin>>s1>>s2;
	for(int i=0;i<n;i++){
		v[s1[i]].push_back(i+1);
	}
	for(int i=1;i<=n;i++){
		a[i]=v[s2[i-1]][cnt[s2[i-1]]++];
	}
	for(int i=1;i<=n;i++){
		ans+=query(n)-query(a[i]);
		update(a[i]);
	}
	cout<<ans;
	return 0;
}