记录编号	252063	评测结果	AAAAAAAAAA
题目名称	[HAOI 2009]求回文串	最终得分	100
用户昵称	thomount	是否通过	通过
代码语言	C++	运行时间	0.314 s
提交时间	2016-04-19 11:44:20	内存使用	16.50 MiB

#include <cstdio>
#include <cstring>
const int M = 30, N = 1000010;
int ss[M], tt[M], ns[M], id[N], left[N], t[N], w[N], n;
char s[N];
inline void add(int x) {while (x <= n) t[x] ++, x += x & (-x);}
inline int check(int x) {int ans = 0; while (x) ans += t[x], x -= x & (-x); return ans;}
int main() {
	freopen("string!.in", "r", stdin);
	freopen("string!.out", "w", stdout);
	scanf("%s", s+1); n = strlen(s+1);
	memset(ss, 0, sizeof(ss));
	for (int i = 1; i <= n; i++) ss[s[i] - 'A']++;
	int flag = 0; tt[0] = 0;
	for (int i = 1; i <= 26; i++) tt[i] = tt[i-1] + ((ss[i-1]+1) >> 1);
	for (int i = 0; i < 26; i++) if (ss[i] & 1) flag++;
	if ((n & 1) != flag) {printf("-1\n"); return 0;}
	memset(ns, 0, sizeof(ns));
	for (int i = 1; i <= n; i++) {
		int x = s[i] - 'A'; ns[x]++;
		if ((ns[x] << 1) == ss[x]+1) id[i] = tt[x] + ns[x], left[i] = 2;
		if ((ns[x] << 1) < ss[x]+1) id[i] = tt[x] + ns[x], left[i] = 1;
		if ((ns[x] << 1) > ss[x]+1) id[i] = tt[x]+ss[x]-ns[x]+1, left[i] = 0;
	}
	long long ans = 0; int tot = 0;
	if (n & 1) for (int i = 1; i <= n && left[i] != 2; i++) if (!left[i]) ans++;
	for (int i = 1; i <= n; i++) if (left[i] == 1) ans += i - (++tot), w[id[i]] = tot;
	for (int i = 1; i <= n; i++) if (!left[i]) ans += check(w[id[i]]-1), add(w[id[i]]);
	printf("%lld\n", ans);
	return 0;
}