[牛客练习赛64][F. 如果我让你查回文你还爱我吗]

虽然已经退役了，但还是要写写博客的，先定个小目标：一年至少更一篇（x

题目链接：https://ac.nowcoder.com/acm/contest/5633/F

题目大意：给定一个长度为 $n$ 的仅包含小写字母的字符串 $S$ 以及 $Q$ 次询问 $(l,r)$ ：有多少对不同的整数 $x,y$ 满足 $l\le x\le y\le r$ ，且 $S_x,S_{x+1},\cdots,S_{y?1},S_y$ 构成一个回文串。下标从 $1$ 开始。

题解：先不考虑一些边界的细节，直接考虑先用manacher求出 $r[i]$ 表示以每个位置为中点的最长回文半径，再来看下对每次询问答案的式子是什么样的。为避免重名，下面默认询问区间为 $(L,R)$ 。

　　　枚举以每个位置作为回文串中心时的贡献，分析一下是 $\min(r[i],i-L,R-i)$ 的求和。这里是三个数字取最小值不太方便，于是考虑分两边计算。设 $m=\frac{L+R}{2} $ 为询问区间的中点，那么对于左半部分，每个位置的贡献就是 $\min(r[i],i-L)$ ，右半部分的贡献则是 $\min(r[i],R-i)$ 。为了方便计算，我们对式子进行变形，左半部分变成 $\min(r[i]-i,-L)+i$ ，右半部分变成 $\min(r[i]+i,R)-i$ 。

　　　在经过上述的处理后，题目就变为了若干次区间询问 $\sum{\min(w[i],Q)\pm i} $ ，其中 $w[i]$ 是我们预处理得到的仅跟 $i$ 有关的数组，而在这其中， $\sum \pm i$ 又是可以直接计算的，所以最后我们就是要处理形如 $\sum{\min(w[i],Q)}$ 的询问。

　　　具体地，对于每次 $(L,R)$ 的查询，我们需要计算两个算式的值： $q1=\sum_{i=L}^{m} {\min(r[i]-i,-L)},q2=\sum_{i=m+1}^{R} {\min(r[i]+i,R)}$ 。注意到每次询问的 $Q$都是与区间端点相关的，故考虑离线处理。

　　　以左半部分的询问为例，将询问按左端点排好序后，使用树状数组维护两个值：区间内 $\min(r[i]-i,-L)$ 取值为 $-L$ 的位置个数，以及区间内尚未取到 $-L$ 的每个位置对应 $r[i]-i$ 的和。随着 $L$ 的增加，取值为 $-L$ 的位置会越来越多，每次把取到 $-L$ 的位置在其中一个树状数组置零，另外一个树状数组标记为 $1$ 即可。对于右半部分的询问也进行类似的操作就好。

 1 #include
 2 using namespace std;
 3 #define N 400020
 4 #define LL long long
 5 LL n,q,r[N],s[N],L,R,m,mx,id,ans[N],a[N],b[N],sl[N],sr[N];
 6 vectordl[N],dr[N];
 7 vector>ql[N],qr[N];
 8 struct BIT
 9 {
10     LL t[2][N];
11     LL lowbit(LL x){return x&(-x);}
12     void cg(LL o,LL x,LL c){while(xlowbit(x);}
13     LL ask(LL o,LL x){LL r=0;while(x)r+=t[o][x],x-=lowbit(x);return r;}
14     LL ask(LL o,LL l,LL r){return ask(o,r)-ask(o,l-1);}
15     LL query(LL k,LL l,LL r){return ask(0,l,r)+k*ask(1,l,r);}
16 }tl,tr;
17 int main()
18 {
19     scanf("%lld%lld",&n,&q);
20     for(LL i=1;i<=n;i++){
21         char ch=getchar();
22         while(ch<'a' || ch>'z')ch=getchar();
23         s[i*2-1]=ch-'a'+1;
24         s[i*2]=27;
25     }
26     n=n*2-1,s[0]=27;
27     for(LL i=1;i<=n;i++){
28         r[i]=1;
29         if(mx>i)r[i]=min(r[2*id-i],mx-i+1);
30         while(0<=i-r[i] && i+r[i]<=n+1 && s[i+r[i]]==s[i-r[i]])r[i]++;
31         if(i+r[i]-1>mx)mx=i+r[i]-1,id=i;
32     }
33     for(LL i=1;i<=n;i++){
34         r[i]=r[i]/2;
35         if(i&1)a[i]=r[i]-i/2-1;else a[i]=r[i]-i/2;
36         b[i]=r[i]+i/2-1;
37         if(a[i]>=0)a[i]=0,tl.cg(1,i,1);
38         else dl[-a[i]*2].push_back(i),tl.cg(0,i,a[i]);
39         if(b[i]>=(n+1)/2)b[i]=(n+1)/2,tr.cg(1,i,1);
40         else dr[b[i]*2].push_back(i),tr.cg(0,i,b[i]);
41         sl[i]=sl[i-1]+(i&1?i/2+1:i/2);
42         sr[i]=sr[i-1]+(1-i/2);
43     }
44     for(LL i=1;i<=q;i++){
45         scanf("%lld%lld",&L,&R);
46         m=L+R-1,L=L*2-1,R=R*2-1;
47         ans[i]+=sl[m]-sl[L-1]+sr[R]-sr[m];
48         ql[L].push_back(make_pair(i,m));
49         qr[R].push_back(make_pair(i,m));
50     }
51     for(LL i=1;i<=n;i++){
52         for(auto j:dl[i])tl.cg(0,j,-a[j]),tl.cg(1,j,1);
53         for(auto pi:ql[i])ans[pi.first]+=tl.query(-i/2,i,pi.second);
54     }
55     for(LL i=n;i>=1;i--){
56         for(auto j:dr[i])tr.cg(0,j,-b[j]),tr.cg(1,j,1);
57         for(auto pi:qr[i])ans[pi.first]+=tr.query(i/2,pi.second+1,i);
58     }
59     for(LL i=1;i<=q;i++)printf("%lld\n",ans[i]);
60 }

边界情况的细节需要注意，因为manacher会把坐标全部乘二，所以询问区间的中点一定是整数，但是对应的，式子中与 $ i$ 相关的计算就需要花点工夫分类讨论了。