40pts求调(trie+树状数组逆序对)
查看原帖
40pts求调(trie+树状数组逆序对)
605226
modfisher楼主2023/8/1 21:25
#include <cstdio>
#include <iostream>
#include <string>

using namespace std;

const int maxn = 1e5 + 5;

int n;
int trie[maxn * 5][52], cnt = 0, num[maxn], rel[maxn];
long long tr[maxn];

int turn(char c){
	if(c >= 'A' && c <= 'Z') return c - 'A';
	if(c >= 'a' && c <= 'z') return c - 'a' + 26;
	return -1;
}
int insert(string s){
	int x = 0;
	for(int i = 0; i < s.size(); i ++){
		if(!trie[x][turn(s[i])]) trie[x][turn(s[i])] = ++ cnt;
		x = trie[x][turn(s[i])];
	}
	return x;
}
int search(string s){
	int x = 0;
	for(int i = 0; i < s.size(); i ++){
		if(!trie[x][turn(s[i])]) return 0;
		x = trie[x][turn(s[i])];
	}
	return x;
}
int lb(int x){
	return x & (-x);
}
void add(int x, int id){
	for(int i = id; i <= n; i += lb(i)){
		tr[i] += x;
	}
}
long long query(int id){
	long long s = 0;
	for(int i = id; i > 0; i -= lb(i)){
		s += tr[i];
	}
	return s;
}

int main(){
	scanf("%d", &n);
	for(int i = 1; i <= n; i ++){
		string s;
		cin >> s;
		num[insert(s)] = i;
	}
	for(int i = 1; i <= n; i ++){
		string s;
		cin >> s;
		rel[i] = num[search(s)];
	}
	long long ans = 0;
	for(int i = 1; i <= n; i ++){
		add(1, rel[i]);
		ans += i - query(rel[i]);
	}
	printf("%lld", ans);
	return 0;
}

过了前4个点

2023/8/1 21:25
加载中...