提交记录

#include<bits/stdc++.h>
using namespace std;
#define N 60010
#define M 26
int n,m,a[N],pos[N],L[N],R[N],t,sum[1<<M],cnt[1<<M],p2[M],ans,s[N];
struct pro
{
	int id,pl,l,r;
	bool operator<(const pro&b)const
	{
		if(pl==b.pl) return r<b.r;
		else return pl<b.pl;
	}  
}p[N];
void add(int x)
{
	ans+=cnt[sum[x]];cnt[sum[x]]++;
	for(int i=0;i<M;i++) ans+=cnt[sum[x]^p2[i]];
}
void del(int x)
{
	cnt[sum[x]]--;ans-=cnt[sum[x]];
	for(int i=0;i<M;i++) ans-=cnt[sum[x]^p2[i]];	
}
int main()
{
	//freopen("1.in","r",stdin);
//	freopen("1.out","w",stdout);
	cin>>n>>m;char ch;getchar();t=3*sqrt(n);
	for(int i=1;i<=t;i++) L[i]=(i-1)*t+1,R[i]=i*t;
	if(R[t]<n) t++,L[t]=R[t-1]+1,R[t]=n;
	for(int k=1;k<=t;k++)
	  for(int i=L[k];i<=R[k];i++) pos[i]=k;
	for(int i=1;i<=n;i++)scanf("%1c",&ch),a[i]=ch-'a';
	for(int i=1;i<=n;i++) sum[i]=sum[i-1]^(1<<a[i]); 
	for(int i=0;i<M;i++) p2[i]=(1<<i);
	for(int i=1;i<=m;i++)
	{
		int l,r;scanf("%d%d",&l,&r);
		p[i]=(pro){i,pos[l],l,r};
	}
	sort(p+1,p+m+1);int l=1,r=0;
	for(int i=1;i<=m;i++)
	{
		int x=p[i].l-1,y=p[i].r;
		while(l>x) add(--l);
		while(r<y) add(++r);
		while(l<x) del(l++);
		while(r>y) del(r--);
		s[p[i].id]=ans;
	}
	for(int i=1;i<=m;i++) printf("%d\n",s[i]);
	return 0;
}