记录编号	175996	评测结果	AAAAAAAAAA
题目名称	[HAOI 2009]求回文串	最终得分	100
用户昵称	stdafx.h	是否通过	通过
代码语言	C++	运行时间	1.136 s
提交时间	2015-08-07 19:15:58	内存使用	8.64 MiB

#define MAXN 1000010UL
#define MAXC 28UL

#define M(q) (q-'A')

#include <cstdio>
#include <cstring>
#include <deque>

char sp,s[MAXN],new_s[MAXN];

int nl,length,np[MAXN],tree[MAXN];

long long ANS;

bool ex[MAXN];

std::deque<int> p[MAXC];

void update(int p){
	for(;p<=length;p+=p&(-p)){
		tree[p]++;
	}
	return;
}

int getsum(int p){
	int Ans=0;
	for(;p>0;p-=p&(-p)){
		Ans+=tree[p];
	}
	return Ans;
}

int main(){
	freopen("string!.in","r",stdin);
	freopen("string!.out","w",stdout);
	scanf("%s",s+1);
	length=strlen(s+1);
	for(int i=1;i<=length;i++){
		p[M(s[i])].push_back(i);
	}
	for(int i=1;i<=length;i++){
		if(!ex[i]){
			int tmp=M(s[i]);
			if(p[tmp].size()==1){
				sp=s[i];p[tmp].pop_front();
			}
			else{
				new_s[++nl]=s[i];
				ex[p[tmp].back()]=1;
				p[tmp].pop_back();p[tmp].pop_front();
			}
		}
	}
	new_s[++nl]=sp;
	nl<<=1;nl--;
	for(int i=(nl>>1)+2;i<=nl;i++){
		new_s[i]=new_s[nl-i+1];
	}
	for(int i=1;i<=nl;i++){
		p[M(new_s[i])].push_back(i);
	}
	for(int i=1;i<=length;i++){
		np[i]=p[M(s[i])].front();p[M(s[i])].pop_front();
	}
	for(int i=1;i<=length;i++){
		update(np[i]);
		ANS+=i-getsum(np[i]);
	}
	printf("%lld",ANS);
	return 0;
}