题解 P3604 【美好的每一天】

· · 题解

莫队

注意到回文串只可能是所有字母都是偶数个或者仅有一个字母是奇数个

由于区间内我们只关心字母的奇偶，想到异或

对于一个区间我们用一个26位的二进制数表示每一个字母出现次数为奇或偶(0偶1奇)

而我们只要把所有的前缀区间的状态计算出来，对于任意一个区间我们都可以异或得到答案

定义a_i表示区间[1,i]的各个字母出现状态的值

[x,y]的状态即a_y\bigoplus a_{x-1}

那么其实原问题就被我们转换成对于一个区间[x,y]

选择i属于[x-1,y]的两个不同位置的a值进行异或是否能得到0或者2的某次方

得到0即字母都是奇数个，2的某次方即仅有一个字母是奇数个

我们考虑莫队区间拓展的过程

进来一个值时相当于多了一个a值x可用

根据异或的传递性，我们查询原本这个区间里a值等于x的有多少和a值等于x异或2的某次方的有多少

删除同理

复杂度O(26*n\sqrt n)

#include<bits/stdc++.h>
using namespace std;
const int maxn=60005,maxm=60005;
int n,m;
int base;
struct query{
    int id;
    int x,y;
    bool operator <(query i)const{
        return x/base==i.x/base?y<i.y:x<i.x;
    }
}q[maxm];
int ans=0;
int a[maxn];
int cnt[(1<<26)+5];
int ANS[maxm];
inline int read(){
    register int x=0,y=1;
    register char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')y=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return x*y;
}
inline void ins(register int x){
    ans+=cnt[a[x]];
    cnt[a[x]]++;
    for(register int i=0;i<26;i++)
        ans+=cnt[a[x]^(1<<i)];
    return ;
}
inline void del(register int x){
    cnt[a[x]]--;
    ans-=cnt[a[x]];
    for(register int i=0;i<26;i++)
        ans-=cnt[a[x]^(1<<i)];
    return ;
}
int main(){
    n=read();m=read();
    base=3*sqrt(n);
    for(register int i=1;i<=n;i++){
        register char c;
        cin>>c;
        a[i]=1<<(c-'a');
        a[i]^=a[i-1];
    }
    for(register int i=1;i<=m;i++){
        q[i].id=i;
        q[i].x=read();
        q[i].y=read();
    }
    sort(q+1,q+m+1);
    int l=1,r=0;
    for(register int i=1;i<=m;i++){
        register int x=q[i].x-1,y=q[i].y,id=q[i].id;
        while(l<x)del(l++);
        while(l>x)ins(--l);
        while(r>y)del(r--);
        while(r<y)ins(++r);
        ANS[id]=ans;
    }
    for(register int i=1;i<=m;i++)printf("%d\n",ANS[i]);
    return 0;
}