[bzoj2119][后缀数组][ST表]股市的预测

Description

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

Input

第一行包含两个整数N、M，分别表示需要统计的总时间以及重现的间隔（B部分的长度）。 接下来N行，每行一个整数，代表每一个时间点的股价。
4≤N≤50000 1≤M≤10 M≤N 所有出现的整数均不超过32位含符号整数。

Output

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

Sample Input

12 4

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

Sample Output

6

HINT

【样例说明】

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

题解

听说这是个套路…
首先差分后就变为要计数形如$ABA$的串，其中$B$的长度固定
然后考虑暴力怎么做
可以枚举一个$A$的长度，然后枚举第一个$A$在哪里开始的
显然可以$O(1)$知道下一个位置是不是合法的…然后就是一个优秀的 n 2 n^2 n2
需要优化
枚举$A$的长度后，我们把这个序列隔A分段，就是$1,A,2A...$
然后枚举断点，不妨设位置为$x$，长度为$i$
显然在位置$x$的地方应该check的下一个位置是$y=x+m+i$
求一下他们的$lcp$和$lcs$，长度设为$u1,u2$
显然仅有在$[x-u1+1,x+u2-1]$这一段与后面有对应相同
那么这个$x$就可以在上面这一段移动了，显然后面的$y$也有跟随移动的方式使得能产生一段合法的$A$
手玩一下合法的$x$就只有$u1+u2-i$这么多个位置可以移动
注意$u1,u2$对$i$取$min$，因为不能取到下一个或者上一个断点不然会算重
预处理SA和rmq后就是$nlogn$的了

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define LL long long
#define mp(x,y) make_pair(x,y)
#define pll pair
#define pii pair
using namespace std;
inline int read()
{int f=1,x=0;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;
}
int stack[20];
inline void write(LL x)
{if(x<0){putchar('-');x=-x;}if(!x){putchar('0');return;}int top=0;while(x)stack[++top]=x%10,x/=10;while(top)putchar(stack[top--]+'0');
}
inline void pr1(int x){write(x);putchar(' ');}
inline void pr2(LL x){write(x);putchar('\n');}
const int MAXN=200005;int A[MAXN],B[MAXN],n,m,LS[MAXN],lslen;
int Rsort[MAXN],sa1[MAXN],sa2[MAXN],Rank[MAXN],tt[MAXN];
void getsa(int len,int m)
{memcpy(Rank,B,sizeof(Rank));for(int i=1;i<=len;i++)Rsort[Rank[i]]++;for(int i=1;i<=m;i++)Rsort[i]+=Rsort[i-1];for(int i=len;i>=1;i--)sa1[Rsort[Rank[i]]--]=i;int ln=1,p=0;while(p<len){int k=0;for(int i=len-ln+1;i<=len;i++)sa2[++k]=i;for(int i=1;i<=len;i++)if(sa1[i]-ln>=1)sa2[++k]=sa1[i]-ln;memset(Rsort,0,sizeof(Rsort));for(int i=1;i<=len;i++)Rsort[Rank[i]]++;for(int i=1;i<=m;i++)Rsort[i]+=Rsort[i-1];for(int i=len;i>=1;i--)sa1[Rsort[Rank[sa2[i]]]--]=sa2[i];memcpy(tt,Rank,sizeof(tt));Rank[sa1[1]]=p=1;for(int i=2;i<=len;i++){if(tt[sa1[i]]!=tt[sa1[i-1]]||tt[sa1[i]+ln]!=tt[sa1[i-1]+ln])p++;Rank[sa1[i]]=p;}m=p;ln<<=1;}
}
int height[MAXN];
void gethe(int len)
{int j,k=0;for(int i=1;i<=len;i++){j=sa1[Rank[i]-1];if(k)k--;while(B[i+k]==B[j+k])k++;height[Rank[i]]=k;}
}
int bin[25],Log[MAXN],mn[25][MAXN];
void init(int len)
{for(int i=1;i<=len;i++)mn[0][i]=height[i];for(int i=1;bin[i]<=len;i++)for(int x=1;x+bin[i]-1<=len;x++)mn[i][x]=min(mn[i-1][x],mn[i-1][x+bin[i-1]]);
}
int getmn(int l,int r)
{l=Rank[l];r=Rank[r];if(l>r)swap(l,r);l++;int K=Log[r-l+1];return min(mn[K][l],mn[K][r-bin[K]+1]);
}
int fac[MAXN];
int main()
{bin[0]=1;for(int i=1;i<=20;i++)bin[i]=bin[i-1]<<1;Log[1]=0;for(int i=2;i<MAXN;i++)Log[i]=Log[i>>1]+1;n=read();m=read();for(int i=1;i<=n;i++)A[i]=read();B[1]=998244353;for(int i=2;i<=n;i++)B[i]=A[i]-A[i-1],LS[++lslen]=B[i];LS[++lslen]=B[1];sort(LS+1,LS+1+lslen);lslen=unique(LS+1,LS+1+lslen)-(LS+1);for(int i=1;i<=n;i++)B[i]=lower_bound(LS+1,LS+1+lslen,B[i])-(LS);for(int i=n;i>=1;i--)B[(n-i+1)+n+1]=B[i],fac[i]=(n-i+1)+n+1;B[n+1]=++lslen;
//	for(int i=1;i<=2*n+1;i++)printf("%d ",B[i]);int ln=2*n+1;getsa(ln,lslen);gethe(ln);init(ln);LL ans=0;for(int i=1;i<n;i++){for(int x=2;x<=n;x+=i){int y=x+i+m;int u1=getmn(x,y),u2=getmn(fac[x],fac[y]);u1=min(u1,i),u2=min(u2,i);if(u1&&u2){if(u1+u2>i)ans+=u1+u2-i;}else if(u1||u2){if(u1>i)ans+=u1-i;if(u2>i)ans+=u2-i;}}}pr2(ans);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！