【题解】洛谷P3531： [POI2012] LIT-Letters

P3531 [POI2012] LIT-Letters

写了个假做法有点伤心，本以为是两个都求逆序对然后答案相减，但是这样在部分数据上确实合法，但是实际上毫无章法没有逻辑。

正解考虑贪心，我们一个数字肯定要找最前面，第二次出现就去最前面第二次出现的位置，因为如果第一个A放在了后面，那么就有可能产生更对逆序对（因为你把大的数放在了前面）。

我们对每个字母重新编号，\(A\) 为 ABC 编号为 123，\(B\) 为 CBA 编号为 321。

接下来就可以正常求逆序对了。

其实思想就是多个重复的我们进行去重，让他们有对应的编号，像原来为A为010,B为100,完全没法去逆序对，不知道的还以为是区间差呢，但是我们重编号就为123,213这就很明确了，我们都尽量向前靠，每个数该去哪就去哪。

#include<bits/stdc++.h>
#define int long long
#define ls p<<1
#define rs p<<1|1 
#define re register 
const int N=1e6+10;
const int mod=998244353;
using namespace std;

int n;

int a[N],b[N];
 

int t[N];

int lb(int x){
	return x&-x;
}

void add(int x,int k){
	while(x<=n){
		t[x]+=k;
		x+=lb(x);
	}
}

int query(int x){
	int sum=0;
	while(x){
		sum+=t[x];
		x-=lb(x);
	}
	return sum;
}

int vis[30][N];
int tt[100]; 

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr); 
	
	cin>>n;
	
	for(int i=1;i<=n;i++){
		char c;
		cin>>c;
		a[i]=c-'A'+2;
	}
	for(int i=1;i<=n;i++){
		char c;
		cin>>c;
		b[i]=c-'A'+2;
	}
	
	for(int i=1;i<=n;i++){
		vis[a[i]][++vis[a[i]][0]]=i;
	} 
	for(int i=1;i<=n;i++){
		b[i]=vis[b[i]][++tt[b[i]]];
	} 
	int ans=0;
	for(int i=n;i>=1;i--){
		ans+=query(b[i]-1);
		add(b[i],1);
	}
	cout<<ans;
	
	return 0;
}