【BZOJ4866】[YNOI2017] 由乃的商场之旅（莫队）

点此看题面

大致题意： 给你一个字符串，每次给你一段区间，问这段区间内有多少个字符串在重新排列后可以变成一个回文串。

关于莫队

详见这篇博客：莫队算法学习笔记（一）——普通莫队。

关于回文

要使一个字符串在重新排列后可以变成一个回文串，其实只有两种情况：

所有字符都出现了偶数次。
只有一个字符出现了奇数次，其余字符都出现了偶数次。

关于状压

我们可以用一个\(26\)位的二进制数\(sum_i\)表示\(1\sim i\)范围内每一个字符出现的次数是奇数还是偶数，并用\(cnt_i\)存储状态\(i\)出现的次数。

则不难发现，设当前新加入/删除了一个数\(x\)，则改变的贡献值就相当于：\(cnt_x+\sum_{i=0}^{25}cnt_{x\text{^}(1<<i)}\)，这应该还是比较好理解的，就相当于枚举哪一个数出现了奇数次。

顺便提一下，为了卡常，这个式子可以循环展开。

关于内存

不难发现，如果开一个大小为\(2^{26}\)的\(int\)数组，会\(MLE\)。

如果开成\(short\)，\(cnt_i\)最大为\(60000\)，\(short\)显然存不下。

于是我们就要开\(unsigned\ short\)，这样就既不会\(MLE\)，也不会\(WA\)了。

关于常数

此题似乎略卡常数。

本来即使用了上面提到过的循环展开还是一直\(TLE\)，后来发现忘记加莫队一个比较实用的小\(trick\)，即在排序时分奇数块与偶数块讨论，一加压时限\(19052ms\)过了。

\(hl666\)神犇告诉我，这题块的大小要开\(2\sqrt N\)，一用，果然快了很多，变成了\(16740ms\)。

代码

#include<bits/stdc++.h>

#define N 60000

#define min(x,y) ((x)<(y)?(x):(y))

using namespace std;

int n,query_tot,a[N+5],Shl[30];

class Class_FIO

{

    private:

        #define Fsize 100000

        #define tc() (A==B&&(B=(A=Fin)+fread(Fin,1,Fsize,stdin),A==B)?EOF:*A++)

        #define pc(ch) (void)(FoutSize<Fsize?Fout[FoutSize++]=ch:(fwrite(Fout,1,Fsize,stdout),Fout[(FoutSize=0)++]=ch))

        int Top,FoutSize;char ch,*A,*B,Fin[Fsize],Fout[Fsize],Stack[Fsize];

    public:

        Class_FIO() {A=B=Fin;}

        inline void read(int &x) {x=0;while(!isdigit(ch=tc()));while(x=(x<<3)+(x<<1)+(ch&15),isdigit(ch=tc()));}

        inline void reads(string &x) {x="";while(isspace(ch=tc()));while(x+=ch,!isspace(ch=tc()));}

        inline void writeln(int x) {if(!x) return pc('0'),pc('\n');while(x) Stack[++Top]=x%10+48,x/=10;while(Top) pc(Stack[Top--]);pc('\n');}

        inline void clear() {fwrite(Fout,1,FoutSize,stdout),FoutSize=0;}

}F;

class Class_CaptainMotao//莫队

{

    private:

        #define POW 67108864

        #define S(p) cnt[x^Shl[p]]

        #define Add(val) res+=cnt[x=a[val]]++,res+=S(0)+S(1)+S(2)+S(3)+S(4)+S(5)+S(6)+S(7)+S(8)+S(9)+S(10)+S(11)+S(12)+S(13)+S(14)+S(15)+S(16)+S(17)+S(18)+S(19)+S(20)+S(21)+S(22)+S(23)+S(24)+S(25)//加一个新的元素

        #define Del(val) res-=--cnt[x=a[val]],res-=S(0)+S(1)+S(2)+S(3)+S(4)+S(5)+S(6)+S(7)+S(8)+S(9)+S(10)+S(11)+S(12)+S(13)+S(14)+S(15)+S(16)+S(17)+S(18)+S(19)+S(20)+S(21)+S(22)+S(23)+S(24)+S(25)//删除一个原有的元素

        int res,block_size,ans[N+5];unsigned short cnt[POW];

    public:

        struct Query

        {

            int l,r,pos,bl;

            inline friend bool operator < (Query x,Query y) {return x.bl^y.bl?x.bl<y.bl:(x.bl&1?x.r<y.r:x.r>y.r);}//注意加上这个十分实用的小trick

        }q[N+5];

        inline void Solve()

        {

            register int i,j,x,L=1,R=0;

            for(block_size=min(n,2*sqrt(n)),i=1;i<=query_tot;++i) F.read(q[i].l),F.read(q[i].r),--q[i].l,q[q[i].pos=i].bl=(q[i].l-1)/block_size+1;//读入

            for(sort(q+1,q+query_tot+1),i=1;i<=query_tot;++i)

            {

                while(R<q[i].r) Add(++R);while(L>q[i].l) Add(--L);while(R>q[i].r) Del(R--);while(L<q[i].l) Del(L++);

                ans[q[i].pos]=res;//记录答案

            }

            for(i=1;i<=query_tot;++i) F.writeln(ans[i]);//输出答案

        }

}C;

int main()

{

    register int i;register string st;

    for(i=Shl[0]=1;i<26;++i) Shl[i]=Shl[i-1]<<1;

    for(F.read(n),F.read(query_tot),F.reads(st),i=1;i<=n;++i) a[i]=a[i-1]^Shl[st[i-1]-97];//a[i]存储前缀异或和

    return C.Solve(),F.clear(),0;

}

巴特西