[DS记录]P3604 美好的每一天
command_block
2021-06-28 08:44:57
**题意** ; 给出一个长度为 $n$ 的字符串 $S$， $q$ 次询问 $S[l,r]$ 有多少个子串在重排后可能形成回文串。
$n,q\leq 6\times 10^4$ ，字符集为小写英文字母。时限$\texttt{3s}$ ，空限$\texttt{160M}$。
------------
考虑一个字符串重排后可能形成回文串的充要条件 ： 出现次数为奇数的字符个数 $\leq 1$。
记 $w_i$ 表示前缀 $S[1,i]$ 的各个字符出现次数的奇偶性，压成一个 $\Sigma$ 位的二进制数。
使用莫队，当区间 $[l+1,r]\rightarrow [l,r]$ 时，答案变化量为 ：
$$\sum\limits_{i=l}^r\Big[\big|w_{l-1}{\ \rm xor\ } w_{i}\big|\leq 1\Big]$$
满足 $|x|\leq 1$ 的二进制数只有 $O(\Sigma)$ 个。再用桶维护每个二进制数出现的次数即可支持 $O(\Sigma)$ 查询。
这个桶的大小为 $O(2^{\Sigma})$ ，有点太大了。本质不同的修改只有 $O(n)$ 种，询问只有 $O(n\Sigma)$ 种，使用离散化即可节省空间。
接着使用二次离线莫队。
考虑如何 $O(1)$ 查询。我们将修改向能贡献到的查询连边，可以证明去重之后，每个修改只会对应 $O(\Sigma)$ 个查询。
这样，我们让修改主动贡献，即可 $O(\Sigma)$ 修改，$O(1)$ 查询。
复杂度 $O(n\sqrt{n}+n\Sigma\log n)$。
```cpp
#include<algorithm>
#include<cstdio>
#include<vector>
#include<cmath>
#define pb push_back
#define ll long long
#define MaxN 60500
using namespace std;
char str[MaxN];
struct Data{int l,r,p;};
vector<Data> b[MaxN];
int n,w[MaxN],x[MaxN],o[MaxN],to[MaxN][30],top[MaxN],sl[MaxN];
ll ans[MaxN];
void calc()
{
w[0]=0;
for (int i=1;i<=n;i++)
x[i]=w[i]=w[i-1]^(1<<(str[i]-'a'));
x[n+1]=0;sort(x+1,x+n+2);
int tn=unique(x+1,x+n+2)-x-1;
for (int i=1;i<=tn;i++){
to[i][top[i]=0]=i;
for (int k=0;k<26;k++){
int tc=x[i]^(1<<k)
,tp=lower_bound(x+1,x+tn+1,tc)-x;
if (x[tp]==tc)to[i][++top[i]]=tp;
}
}
w[0]=sl[0]=1;
for (int k=0;k<=top[1];k++)o[to[1][k]]++;
for (int i=1;i<=n;i++){
w[i]=lower_bound(x+1,x+tn+1,w[i])-x;
for (int k=0;k<=top[w[i]];k++)o[to[w[i]][k]]++;
sl[i]=o[w[i]];
for (int j=0;j<b[i].size();j++){
Data now=b[i][j];ll buf=0;
for (int k=now.l;k<=now.r;k++)
buf+=o[w[k-1]]-sl[k-1];
if (now.p>0)ans[now.p]+=buf;
else ans[-now.p]-=buf;
}
}for (int i=1;i<=n;i++){b[i].clear();o[i]=0;}
}
Data s[MaxN];int BS,m;
bool cmp(const Data &A,const Data &B)
{return A.l/BS==B.l/BS ? ((A.l/BS)&1 ? A.r<B.r : A.r>B.r) : A.l<B.l;}
int main()
{
scanf("%d%d%s",&n,&m,str+1);
for (int i=1;i<=m;i++){
scanf("%d%d",&s[i].l,&s[i].r);
s[i].p=i;
}
BS=sqrt(n+1);sort(s+1,s+m+1,cmp);
int l=1,r=0;
for (int i=1;i<=m;i++){
if (s[i].l<l){b[r].pb((Data){s[i].l,l-1,s[i].p});l=s[i].l;}
if (r<s[i].r)r=s[i].r;
if (l<s[i].l){b[r].pb((Data){l,s[i].l-1,-s[i].p});l=s[i].l;}
if (s[i].r<r)r=s[i].r;
}
calc();
reverse(str+1,str+n+1);
l=n+1;r=n;
for (int i=1;i<=m;i++){
swap(s[i].l,s[i].r);
s[i].l=n-s[i].l+1;s[i].r=n-s[i].r+1;
if (r<s[i].r)r=s[i].r;
if (s[i].l<l){b[r].pb((Data){s[i].l,l-1,s[i].p});l=s[i].l;}
if (s[i].r<r)r=s[i].r;
if (l<s[i].l){b[r].pb((Data){l,s[i].l-1,-s[i].p});l=s[i].l;}
}calc();
for (int i=1;i<=m;i++)ans[s[i].p]+=ans[s[i-1].p];
for (int i=1;i<=m;i++)
printf("%lld\n",ans[i]);
return 0;
}
```