P3604 美好的每一天

链接

题解

这题思路挺明显的，但是真的卡的我好难受。
能重排形成回文串的区间内出现奇数次的字母不能超过一个，又是lxl出的题，做法就很显然了。
但是还是不停地MLE和TLE，看了题解发现储存 (2^{26}) 种状态的数组可以用unsigned short (0~65535) 。。。。
然后开着O2勉强过了。

(Code)

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N=6e4+10;
int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
char get(){
	char ch=getchar();
	while(ch<'a'||ch>'z') ch=getchar();
	return ch;
}
void print(LL x){
    if(x>9) print(x/10);
    putchar(x%10+'0');
}
int E;
int n,m;
int s[N];
unsigned char g[N];
LL ans[N];
struct query{
	int l,r,id;
}q[N];
unsigned short c[(1<<26)+10];
bool cmp(query x,query y){
	if(g[x.l]!=g[y.l]) return g[x.l]<g[y.l];
	return x.r<y.r;
}
LL now;
inline void add(int x,LL f){
	LL re=0;
	if(f<0) --c[x];
	re=c[x];
	for(register int i=0;i<26;++i) re+=c[x^(1<<i)];
	if(f>0) ++c[x];
	now+=f>0?re:-re;
}
int main(){
	char ch;
	scanf("%d%d",&n,&m);E=sqrt(n)*2;
	for(register int i=1;i<=n;++i){
		ch=get();
		s[i]=s[i-1]^(1<<(ch-'a'));
		g[i]=(i+E-1)/E;
	}
	for(register int i=1;i<=m;++i) {
		q[i].l=read();q[i].r=read();
		q[i].id=i;
	}
	sort(q+1,q+1+m,cmp);
	int l=1,r=0;++c[s[0]];now=0;
	for(register int i=1;i<=m;++i){
		while(l>q[i].l){add(s[l-2],1LL);--l;}
		while(r<q[i].r){add(s[r+1],1LL);++r;}
		while(l<q[i].l){add(s[l-1],-1LL);++l;}
		while(r>q[i].r){add(s[r],-1LL);--r;}
		ans[q[i].id]=now;
	}
	for(register int i=1;i<=m;++i) {
		print(ans[i]);
		puts("");
	}
	return 0;
}