UVALive 6284 Hyperdrome 位运算+has

题意：给一个长度为$3*10^5$的字符串，判断有多个子串$[l,r]$重新排列之后可以是回文串

因为字符是$'a'-'z'$以及$'A'-'Z'$，那么我们可以用一个long long的二进制来标示某个区间该字符出现的次数，如果为奇数对应位则为1，如果为偶数则对应位为0。显然，如果该区间的字符可以重新排列组成回文串，那么该区间内1的个数<=1。
以上，以下。
假设知道区间$[1,r]$的“状态”，那么我们可以找是否存在$l$，使得$[l,r]$的“状态”中1的个数<=1，也就是：
已知$[1,r]$，求
1)$[1,l-1]$^$[l,r]$==0中的$l$的个数
2)$[1,l-1]$^$[l,r]$结果中1的个数=1中的$l$的个数,$l>1$
然后枚举的时候hash保存一下所有的$[1,l]$的值出现的次数
map。。T了。。改后向星过。。。
代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
using namespace std;
int getnum(char ch){
	if(ch>='a'&&ch<='z')return ch-'a';
	else return ch-'A'+26;
}
typedef long long LL;
const int Mod = 100009;
struct Edge {
	LL to;int next,cnt;
	Edge(){}
	Edge(LL _to,int _next,int _cnt):to(_to),next(_next),cnt(_cnt){}
}e[Mod*100];
int head[Mod+10],tot;
void init(){
	memset(head,-1,sizeof(head));
	tot=0;
}
void Add(LL x){
	int t=x%Mod;
	for(int i=head[t];~i;i=e[i].next){
		if(e[i].to==x){
			++e[i].cnt;
			return ;
		}
	}
	e[tot]=Edge(x,head[t],1);
	head[t]=tot++;
}
int GetVal(LL x){
	int t=x%Mod;
	for(int i=head[t];~i;i=e[i].next){
		if(e[i].to==x)return e[i].cnt;
	}
	return 0;
}
//map <LL,int> mm;
//map <LL,int> ::iterator it;
char strs[100000*3 + 100];
int main(){
	int n;
	while(~scanf("%d",&n)){
		scanf("%s",strs);
		LL pre=0;
		init();
		Add(0);
		//mm.clear();
		//mm.insert(pair<LL,int>(0,1));
		LL ans=0;
		for(int i=0;i<n;i++){
			pre^=1LL<<getnum(strs[i]);
			ans+=GetVal(pre);
			//it=mm.find(pre);
			//if(it!=mm.end()){
				//ans+=it->second;
			//}
			for(int i=0;i<52;i++){
				ans+=GetVal(pre^(1LL<<i));
				//it=mm.find(pre^(1LL<<i));
				//if(it!=mm.end()){
					//ans+=it->second;
				//}
			}
			Add(pre);
			//it=mm.find(pre);
			//if(it==mm.end())mm.insert(pair<LL,int>(pre,1));
			//else ++mm[pre];
		}
		printf("%lld\n",ans);
	}
	return 0;
}