记录编号	175936	评测结果	AAAAAAAAAA
题目名称	[HAOI 2009]求回文串	最终得分	100
用户昵称	lenibomb	是否通过	通过
代码语言	C++	运行时间	1.738 s
提交时间	2015-08-07 16:28:37	内存使用	4.58 MiB

#include<cstdio>
#include<cstring>
#include<iostream>
#include<vector>
using namespace std;
string s;
int last[190],pre[190];
int num[190];
int len;
bool vis[1000005];
int sum[1000005];
vector <int> pos[190];
int lowbit(int x){
	return x&(-x);
}
int change(int x,int k){
	while(x<=len){
		sum[x]+=k;
		x+=lowbit(x);
	}
}
int getsum(int x){
	int ans=0;
	while(x>0){
		ans+=sum[x];
		x-=lowbit(x);
	}
	return ans;
}
long long cnt=0;
int main(){
	freopen("string!.in","r",stdin);
	freopen("string!.out","w",stdout);
	string ss="`";
	cin>>s;
	s=ss+s;
	len=s.size()-1;
	for(int i=1;i<=len;i++){
		num[(int)s[i]]++;
		pos[(int)s[i]].push_back(i);
	}
	for(int i=1;i<=len;i++){
		change(i,1);
	}
//	printf("%d",getsum(9)-getsum(7));
	for(int i=1;i<=len;i++){
		if(!vis[i]){
			int t=pos[(int)s[i]][pos[(int)s[i]].size()-1];
		//	printf("%d ",t);
			if(t==i){
				cnt+=(getsum(len)-getsum(i))/2;
			}
			else{
				cnt+=(getsum(len)-getsum(t));
			}
			vis[i]=1;
			vis[t]=1;
			change(i,-1);
			change(t,-1);
			pos[s[i]].erase(pos[s[i]].end()-1);
		//	printf("%d\n",cnt);
		}
	}
	cout<<cnt;
}