题目描述
回归天空是一件庄重的事情，所以卓司决定让大家分批次进行，给每个人给了一个小写字母'a'->'z'作为编号
一个区间的人如果满足他们的编号重排之后可以成为一个回文串，则他们可以一起回归天空，即这个区间可以回归天空
由于卓司是一个喜欢妄想的人，他妄想了m个区间，每次他想知道每个区间中有多少个子区间可以回归天空
因为世界末日要来了，所以卓司的信徒很多
输入格式
第一行两个数n,m
之后一行一个长为n的字符串，代表每个人的编号
之后m行每行两个数l,r代表每次卓司妄想的区间
输出格式
m行，每行一个数表示答案
说明/提示
对于10%的数据，n,m<=100
对于30%的数据，n,m<=2000
对于100%的数据，n,m<=60000
其实一开始还真没有想到用莫队来解决，题目要求区间内所有子区间的回文字符串的个数，之前做过莫队的题目中
https://baichuan./article/details/112676058
这个题比较相似，用异或的性质来处理所有子区间，如果一个字符串是回文串，那么满足只有一个字符或没有任何字符出现的次数为奇数
这也是题目的突破口，预处理时先将字符用前缀异或表示出来，一个二进制数 00011100 ：1 表示该字符出现过 奇数次，0 表示出现过 偶数 次
这样再扩充区间时相当于增加了一个字符串，只需要找到这个字符串与其余区间内是否满足构成回文字符串的条件即可
题目要求的空间太大，所以在这里用 int 空间不够，用 short 又无法表示 1<<26 ，所以采用 unsigned short ，开 O(2) 可以过
const int N=6e4+5;int n,m;int i,j,k;int a[N];struct Query{int l,r;int bel;int id;void read(){ sdd(l,r); }}q[N];int ans[N],ANS,block;int vis[(1<<26)+5]; //unsigned shortbool cmp(Query a,Query b){return a.bel^b.bel?a.l<b.l:a.r<b.r;}void mo(){block=sqrt(n+1);for(int i=1;i<=m;i++) q[i].l--;for(int i=1;i<=m;i++) q[i].bel=q[i].l/block+1;for(int i=1;i<=m;i++) q[i].id=i;sort(q+1,q+1+m,cmp);}void add(int pos){int x=a[pos];ANS+=vis[x]++;for(int i=0;i<26;i++) ANS+=vis[x^(1<<i)];}void del(int pos){int x=a[pos];ANS-=--vis[x];for(int i=0;i<26;i++) ANS-=vis[x^(1<<i)];}int main(){while(~sdd(n,m)){for(int i=1;i<=n;i++){char ch;scanf(" %c",&ch);a[i]=a[i-1]^(1<<ch-'a');}for(int i=1;i<=m;i++) q[i].read();mo();int l=1,r=0; ANS=0;for(int i=1;i<=m;i++){while(l>q[i].l) add(--l);while(r<q[i].r) add(++r);while(l<q[i].l) del(l++);while(r>q[i].r) del(r--);ans[q[i].id]=ANS;}for(int i=1;i<=m;i++) pd(ans[i]);}return 0;}
