题解：P4384 [八省联考 2018] 制胡窜

· · 题解

【题意】 给你一个字符串 S，每次询问给你两个整数 l, r，让你查询有多少个整数对 (i, j), 1 <= i < i + 1 < j <= n，满足 S_{1,i}, S_{i+1,j-1},S_{j,n} 包含 S_{l,r}。

【思路】 感觉直接讨论的细节有一点多，我想偷点懒所以用了容斥。

我们设 f_{i,j,k}(0<=i,j,k<=1) 表示三段里面是否必须包含 S_{l,r}，其中1表示必须。

那么根据容斥，ans=f_{1,0,0}+f_{0,1,0}+f_{0,0,1}-f_{1,1,0}-f_{1,0,1}-f_{0,1,1}+f_{1,1,1}。

只要算出每一项即可。

注意到，如果存在三个与 S_{l,r} 相等的子串，并且两两相交部分不超过 1 ，那么一定是任意整数对都满足条件，我们把这种情况特判一下，剩下的情况就有 f_{1,1,1}=0 。

我们建出 sam ，并且让 S_{l,r} 对应的点为 p，考虑 p 的 endpos 集合，假设其大小为 m。

先说一下，长度为 n 的 S 有 n-1 个空隙，题目等价于找不同的两个空隙把 S 切割开。

1.对于 f_{1,0,0} ，只需要确保选择的空隙都在 ed_1 右边即可。

f_{1,0,0}=\sum_{i=1}^{x-1}\sum_{j=i+1}^x1=\frac{x(x-1)}{2}，其中x=n-ed_1

2.对于 f_{0,0,1} ，只需要确保选择的空隙都在 ed_m-Len+1(Len=r-l+1) 左边即可。

f_{0,0,1}=\frac{x(x-1)}{2},其中x=ed_m-Len

3.对于 f_{0,1,0} 我们只需要枚举 endpos 中间哪一个作为第二段中最先出现的。

f_{0,1,0}=\sum_{i=2}^m(ed_i-ed_{i-1})(n-ed_i)+(ed_1-Len)(n-ed_1) \\ =ed_n*n-\sum_{i=1}^med_i^2+\sum_{i=1}^{m-1} ed_ied_{i+1}-n*Len+len*ed_1

4.对于 f_{1,0,1}，只要保证选择的空隙都在最左边的出现位置和最右边的出现位置之间即可。

f_{1,0,1}=C_x^2,其中x=ed_n-Len-ed_1+1

5.对于 f_{1,1,0}，也是考虑集合 |ed'|=m' 为不与最左边出现位置相交的出现位置的 endpos 集合，然后枚举 ed' 中哪一个是第二段中最先出现的。

f_{1,1,0}=\sum_{i=2}^{m'}(ed'_i-ed'_{i-1})(n-ed'_i)+(ed'_1-Len-T)(n-ed'_1)，其中T=ed_1-1\\ =n*ed'_{m'}-\sum_{i=1}^{m'} {ed'_i}^2+\sum_{i=1}^{m'-1}ed'_{i-1}ed'_{i}-n*Len-T*n+ed'_1*Len+T*ed'_1
  1. 对于 f_{0,1,1}，考虑集合 |ed''|=m'' 为不与最右边出现位置相交的出现位置的 endpos 集合，然后枚举 ed'' 中哪一个是第二段中最后出现的。
=\sum_{i=1}^{m''}ed''_ied''_{i+1}-\sum_{i=1}^{m''}ed_i''^2+ed''_1*Len+T*ed''_n-T*Len

因此，sam 上面用线段树维护 endpos。

值得一题的是，我的代码在洛谷一遍就过了，但是在loj拿了 0 分，测试一下发现本地是对的，但是loj评测机的环境就是错的，我尝试交打印调试信息的代码，结果发现加了几个 cout 输出就正确了，非常奇怪。

后面把线段树上查询时合并 endpos 信息的那里全部写在了函数内，就取得了通过，我现在也没搞清楚。

code1(洛谷AC，lojWA)

code2(洛谷loj都能AC)