MnZn刚学oi,样例不过
  • 板块P5149 会议座位
  • 楼主KAqwq
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/8/7 10:56
  • 上次更新2024/8/7 11:45:50
查看原帖
MnZn刚学oi,样例不过
448018
KAqwq楼主2024/8/7 10:56
#include <bits/stdc++.h>
#define N 500005

typedef long long LL;
LL a[N], n, trie[N][26], pre[N], tot;
char c[N];
inline LL lowbit(LL x) {
	return x & -x;
}
inline void add(LL x, LL y) {
	while (x <= n) {
		a[x] += y;
		x += lowbit (x);
	}
}
inline LL getsum(LL x) {
	LL tmp = 0;
	while (x) {
		tmp += a[x];
		x -= lowbit(x);
	}
	return tmp;
}
inline void update(char c[], LL dep) {
	LL len = strlen(c), p = 0;
	for (LL i = 0; i < len; ++i) {
		LL ch = c[i] - 'a';
		if (!trie[p][ch]) trie[p][ch] = ++tot;
		p = trie[p][ch];
	}
	pre[p] = dep;
}
inline LL query(char c[]) {
	LL len = strlen(c), p = 0;
	for (LL i = 0; i < len; ++i) {
		LL ch = c[i] - 'a';
		p = trie[p][ch];
	}
	return pre[p];
}
int main() {
	std::cin >> n;
	for (LL i = 1; i <= n; ++i) {
		std::cin >> c;
		update(c, i);
	}
	for (LL i = 1; i <= n; ++i) {
		std::cin >> c;
		a[i] = query(c);
	}
	LL ans = 0;
	for (LL i = 1; i <= n; ++i) {
		add(a[i], 1);
		ans += i - getsum(a[i]);
	}
	std::cout << ans;
	return 0;
}

验证码 mbka寄

2024/8/7 10:56
加载中...