bzoj
题解:
后缀数组 + RMQ
有一个性质是, 若出现 ABA 形式, 且 | A | 比较大 | B|<=m, 那么真正的 B 块端点可以来回滑动.
因此我们可以正反做两遍后缀数组, 利用 RMQ 求出区间最小值即前缀长.
然后先枚举 | A|, 再枚举左边 A 的端点, 这样 ABA 位置大体确定.
然后在两个左端点处分别向两端延伸, 更新答案.
时间复杂度 O(nlnn)?
代码:
- #include
- #include
- #include
- #include
- using namespace std;
- #define N 50050
- #define ll long long
- int n,m;
- int a0[N],Log[N];
- struct Pair
- {
- ll x;
- int id;
- }pr[N];
- bool vmp(Pair a,Pair b)
- {
- return a.x<b.x;
- }
- struct node
- {
- int a[N],rank[N],tmp[N],sa[N],hs[N],h[N];
- bool cmp(int i,int j,int k)
- {
- if(i+k>n||j+k>n)return 0;
- return rank[i]==rank[j]&&rank[i+k]==rank[j+k];
- }
- void get_sa()
- {
- int i,cnt=0;
- for(i=1;i<=n;i++)hs[a[i]]++;
- for(i=1;i<=n;i++)if(hs[i])tmp[i]=++cnt;
- for(i=1;i<=n;i++)hs[i]+=hs[i-1];
- for(i=1;i<=n;i++)rank[i]=tmp[a[i]],sa[hs[a[i]]--]=i;
- for(int k=1;cnt!=n;k<<=1)
- {
- for(i=1;i<=n;i++)hs[i]=0;
- for(i=1;i<=n;i++)hs[rank[i]]++;
- for(i=1;i<=n;i++)hs[i]+=hs[i-1];
- for(i=n;i>=1;i--)if(sa[i]>k)tmp[sa[i]-k]=hs[rank[sa[i]-k]]--;
- for(i=1;i<=k;i++)tmp[n-i+1]=hs[rank[n-i+1]]--;
- for(i=1;i<=n;i++)sa[tmp[i]]=i;
- for(i=1,cnt=0;i<=n;i++)tmp[sa[i]]=cmp(sa[i-1],sa[i],k)?cnt:++cnt;
- for(i=1;i<=n;i++)rank[i]=tmp[i];
- }
- }
- void get_h()
- {
- for(int i=1;i<=n;i++)
- {
- if(rank[i]==1)continue;
- for(int j=max(1,h[rank[i-1]]-1);;j++)
- {
- if(a[i+j-1]==a[sa[rank[i]-1]+j-1])h[rank[i]]=j;
- else break;
- }
- }
- }
- int st[N][20];
- void get_st()
- {
- for(int i=1;i<=n;i++)st[i][0]=h[i];
- for(int j=1;j<=18;j++)
- {
- for(int i=1;i+(1<<j)-1<=n;i++)
- {
- st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
- }
- }
- }
- int get_len(int i,int j)
- {
- i=rank[i],j=rank[j];
- if(i>j)swap(i,j);
- i++;
- int LG = Log[j-i+1];
- return min(st[i][LG],st[j-(1<<LG)+1][LG]);
- }
- }p[2];
- int main()
- {
- scanf("%d%d",&n,&m);
- for(int i=1;i<=n;i++)
- scanf("%d",&a0[i]);
- for(int i=2;i<=n;i++)
- Log[i]=Log[i>>1]+1;
- n--;
- for(int i=1;i<=n;i++)
- {
- pr[i].x = 1ll*(a0[i+1]-a0[i]);
- pr[i].id = i;
- }
- sort(pr+1,pr+1+n,vmp);
- ll las;
- for(int k=0,i=1;i<=n;i++)
- {
- if(las!=pr[i].x)
- {
- las = pr[i].x;
- k++;
- }
- p[0].a[pr[i].id]=k;
- }
- for(int i=1;i<=n;i++)p[1].a[i]=p[0].a[n-i+1];
- p[0].get_sa(),p[0].get_h(),p[0].get_st();
- p[1].get_sa(),p[1].get_h(),p[1].get_st();
- int ans = 0;
- for(int len = 1;2*len+m<=n;len++)
- {
- for(int i=1;i+m+len<=n;i+=len)
- {
- int j = i+m+len;
- int l1 = min(p[0].get_len(i,j),len);
- int l2 = min(p[1].get_len(n-i+1,n-j+1),len);
- int tmp=l1+l2-(l1&&l2);
- if(tmp-len>=0)ans+=tmp-len+1;
- }
- }
- printf("%d\n",ans);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2878698.html