Description

墨墨的妈妈热爱炒股，她要求墨墨为她编写一个软件，预测某只股票未来的走势。股票折线图是研究股票的必备工具，它通过一张时间与股票的价位的函数图像清晰地展示了股票的走势情况。经过长时间的观测，墨墨发现很多股票都有如下的规律：之前的走势很可能在短时间内重现！如图可以看到这只股票A部分的股价和C部分的股价的走势如出一辙。通过这个观测，墨墨认为他可能找到了一个预测股票未来走势的方法。进一步的研究可是难住了墨墨，他本想试图统计B部分的长度与发生这种情况的概率关系，不过由于数据量过于庞大，依赖人脑的力量难以完成，于是墨墨找到了善于编程的你，请你帮他找一找给定重现的间隔（B部分的长度），有多少个时间段满足首尾部分的走势完全相同呢？当然，首尾部分的长度不能为零。

Input

输入的第一行包含两个整数N、M，分别表示需要统计的总时间以及重现的间隔（B部分的长度）。接下来N行，每行一个整数，代表每一个时间点的股价。

Output

输出一个整数，表示满足条件的时间段的个数

Sample Input

1
2

12 4
1 2 3 4 8 9 1 2 3 4 8 9

Sample Output

1

6

HINT

六个时间段分别是：3-9、2-10、2-8、1-9、3-11、4-12。

对于100%的数据，4≤N≤50000 1≤M≤10 M≤N 所有出现的整数均不超过32位含符号整数。

Solution

显然题目要求形如ABA的子串的个数。

用一个比较神奇的思路：我们将原串每隔alpha标记一个“关键点”，那么原来长度为alpha的A部分一定被一个且仅有一个关键点定位出来。

假设此点坐标为 i ，此段为A1则A2中对应的点在 i+M+alpha 。

于是我们可以二分从这两个点向左、向右最远延伸到前一个关键点之后，后一个关键点之前的最远的哪里相等，我们记录下这个匹配的长度为len，考虑对答案贡献：

• len < alpha: 此时我们发现它的长度还不能达到我们的期望alpha，贡献为0；
• len >= alpha: 这时他对答案的贡献>0，假设合法的左端点为left, 则 left … left + alpha + M 可以作为合法的答案，以后的 left + i … left + alpha + M + i 都可以作为合法的答案。因为这样的 i 有 len – alpha + 1 个，所以对答案贡献就是len – alpha + 1

时间复杂度：O(N ln N log N)。

实际上，本题可以采用后缀数组+ST表来优化二分，从而做到O(N ln N)的时间复杂度。

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

#include <iostream>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int x=50005;
const ULL s=1000000007;
ULL H[x],T[x],f;
int n,m,a[x],b[x],i,A,p,q,l,r,d,t;
ULL h(int l,int r){return H[r]-H[l-1]*T[r-l+1];}
inline ULL g(int p,int q) {
    if(b[p]!=b[q])return 0;
    for(l=1,r=min(A,p);l<r;){d=(l+r+1)>>1;if(h(p-d+1,p)==h(q-d+1,q))l=d;else r=d-1;}
    for(t=l,l=1,r=min(A,n-q+1);l<r;){d=(l+r+1)>>1;if(h(p,p+d-1)==h(q,q+d-1))l=d;else r=d-1;}
    return max(t+l-A,0);
}
int main(){
    for(T[0]=1,cin>>n>>m,i=1;i<=n;++i)cin>>a[i],T[i]=T[i-1]*s;--n;
    for(i=1;i<=n;++i)b[i]=a[i+1]-a[i],H[i]=H[i-1]*s+b[i];
    for(A=1;(A<<1)<n;++A)for(p=A,q=p+A+m;q<=n;p+=A,q+=A)f+=g(p,q);
    cout<<f;
}