好喜欢 SA + DS。
给出序列 \(a_1\sim a_n\)，有 \(q\) 次询问，每次询问给出 \([l,r]\)，求有多少个区间 \([x,y]\) 满足 \(y-x=r-l\)，\([x,y] \bigcap \,[l,r]=\varnothing\) 且 \(\forall \,i\in[0,r-l],a_{l+i}+a_{x+i}=a_{l}+a_x\)。
\(n,q\le 10^5\)。
tags：
-
\(\text{binary search}\)
-
\(\text{data structures}\)
-
\(\text{string suffix structures}\)
-
\(\color{red}*2900\)
这题看着一点都不串串，但是它就是串串。
原题就是让我们求出有多少个满足条件的左端点。
我们记原数组的差分数组 \(d_i=a_i-a_{i-1}\,(i\in(1,n])\)。认为 \(\boldsymbol{d_1}\) 没有意义，即不存在，其值不与任何一个 \(\boldsymbol{d_i}\) 相同。则满足第二个条件的充要条件是 \(\forall \,i\in(0,r-l],d_{l+i}=-d_{x+i}\)。
- 证明：
根据已知条件可以推出：
\(a_{l+i}+a_{x+i}=a_l+a_x\Leftrightarrow a_{l+i}-a_l=a_x-a_{x+i}\)
\(a_{l+i-1}+a_{x+i-1}=a_l+a_x\Leftrightarrow a_{l+i-1}-a_l=a_{x}-a_{x+i-1}\)
两式相减即可得到 \(a_{l+i}-a_{l+i-1}=a_{x+i-1}-a_{x+i}\)，即 \(d_{l+i}=-d_{x+i}\)。
我们若倍长 \(d\)，且令 \(d_i=-d_{i-n}\,(i\in(n,2n])\)，则上述条件等价于 \(d_{l+i}=d_{x+n+i}\)。我们要统计有多少个 \(x\)，就可以去统计有多少个 \(x+n\)，同理可以去统计有多少个 \(\boldsymbol{x+n+1}\)。
为什么要做这一步转化呢？我们发现，对于 \(d[l+1,2n]\) 和 \(d[x+n+1,2n]\) 这两个后缀，它们存在 \(\boldsymbol{d[l+1,r]}\) 和 \(\boldsymbol{d[x+n+1,x+n+r-l]}\) 这一段长度为 \(\boldsymbol{r-l}\) 的公共前缀。考虑对差分数组进行后缀排序，则可以二分 + ST 表求出与后缀 \(d[l+1,2n]\) 的 \(\text{LCP}\) 长度不小于 \(r-l\) 的排名区间。然后根据不交、长度相等的限制以及差分数组的定义，可以得到 \(x+n+1\) 的范围是 \([n+2,n+2l-r]\bigcup\, [n+r+2,2n+l-r+1]\)。
这就是个二维数点，在线主席树或离线扫描线 + 树状数组维护一下就行了。
- 注意
使用上述统计方法的前提是存在差分数组。当 \(l=r\) 时，区间内不存在差分数组，不能这样统计。
不过容易得知此时答案即为 \(n-1\)，特判一下即可。
代码里用的是主席树，时间、空间复杂度均为 \(\mathcal{O}(n\log n)\)。
提交记录（\(\color{limegreen} \bf{Accepted}\) \(\boldsymbol{483\,\text{ms}\,/\,73952\,\text{KB}}\)，含代码）