记录编号	53757	评测结果	AAAAAAAAAA
题目名称	[HAOI 2009]求回文串	最终得分	100
用户昵称	feng	是否通过	通过
代码语言	C++	运行时间	4.154 s
提交时间	2013-03-05 11:10:03	内存使用	40.37 MiB

#include <cstdio>
#include <cstring>
#include <deque>
#include <algorithm>
#include <iostream>
using namespace std;
const int MAXN=1000005;
const int oo=0x7fffffff;
struct tt{
	int delta,data;
}tree[4000001];
deque<int> q[26];
 
char st[MAXN];
 
int ax,ay,del;
int a[MAXN];
int N;
 
void updata(int left,int right,int root){
    int mid;
    int delta;
    if (ax>right||ay<left) return;
    if (ax<=left&&right<=ay){
        tree[root].data+=del;
        tree[root].delta+=del;
        return;
    }
    mid=(left+right)/2;
    delta=tree[root].delta;
    tree[root*2].delta+=delta;
    tree[root*2].data+=delta;
    tree[root*2+1].data+=delta;
    tree[root*2+1].delta+=delta;
    tree[root].delta=0;
    updata(left,mid,root*2);
    updata(mid+1,right,root*2+1);
    tree[root].data=tree[root*2].data+tree[root*2+1].data;
}
int search(int left,int right,int root){
    int delta;
    int mid,templ,tempr;
    if (ax>right || ay<left) return 0;
    if (ax<=left && right<=ay){
        return tree[root].data;
    }
    mid=(left+right)/2;
    delta=tree[root].delta;
    tree[root*2].delta+=delta;
    tree[root*2].data+=delta;
    tree[root*2+1].data+=delta;
    tree[root*2+1].delta+=delta;
    tree[root].delta=0;
    templ=search(left,mid,root*2);
    tempr=search(mid+1,right,root*2+1);
    return templ+tempr;
}
bool used[MAXN];
int str[MAXN];
int main()
{
	freopen("string!.in","r",stdin);
	freopen("string!.out","w",stdout);
	scanf("%s",st+1);
	int l=1,r=strlen(st+1);
	N=r;
	for(int i=l;i<=r;i++)
		q[str[i]=st[i]-'A'].push_back(i);
	bool flag=false;
	for(int i=0;i<26;i++)
		if (q[i].size()&1)
		{
			if (!flag) flag=true;
			else 
			{
				printf("-1\n");
				return 0;
			}
		}
	long long re=0;
	while(l<r)
	{
		while(used[l])
			l++;
		while(used[r])
			r--;
		if (l>=r)
			break;
		if (str[l]==str[r])
		{
			q[str[l]].pop_front();
			q[str[l]].pop_back();
			l++,r--;
		}
		else
		{
			int w1,w2;
			if (q[str[l]].size()>=2)
			{
				int t=q[str[l]].back();
				ax=t;
				ay=r;
				int tmp=search(1,N,1);
				w1=r-t-tmp;
			}
			else w1=oo;
			if (q[str[r]].size()>=2)
			{
				int t=q[str[r]].front();
				ax=l;
				ay=t;
				int tmp=search(1,N,1);
				w2=t-l-tmp;
			}
			else w2=oo;
			if (w1<w2)
			{
				re+=w1;
				int t=q[str[l]].back();
				ax=t;
				ay=t;
				del=1;
				updata(1,N,1);
				used[t]=true;
				q[str[l]].pop_back();
				q[str[l]].pop_front();
				l++;
			}
			else
			{
				re+=w2;
				int t=q[str[r]].front();
				ax=t;
				ay=t;
				del=1;
				updata(1,N,1);
				used[t]=true;
				q[str[r]].pop_back();
				q[str[r]].pop_front();
				r--;
			}
		}
	}
	cout<<re<<endl;
	//printf("%lld\n",re);
	return 0;
}