BZOJ 2119 股市的預測 後綴數組
題目大意：給定一個序列，求差分後有多少個子串滿足形式為ABA，其中B部分長度為m，A部分長度大於0
首先枚舉A的長度j，將序列上每隔j個點插入一個關鍵點
對於第i個位置上的關鍵點，我們找到第i+j+m個位置
利用後綴數組找出兩個位置向左拓展多少個位置都是相同的，以及向右拓展都少個位置都是相同的
為了保證不重復向左和向右最多拓展j-1個位置
設拓展之後長度為len，那麼如果len>=j，ans+=(len-j+1)
vcG9uPbX07SuPC9wPgo8cD7G5NbQwb249mHL5Mi7z+DNrKOstavKx9PJ09phyvTT2snP0ru49rnYvPy146Os0vK0y86qwcux3MPi1ti4tLzGyv22+LK71NnP8tfzzdjVuTwvcD4KPHA+19y52Lz8tePK/U8obmxvZ24pyrG85Li01NO2yE8obmxvZ24pPC9wPgo8cD48cHJlIGNsYXNzPQ=="brush:java;">#include
#include
#include
#include
#define M 100100
using namespace std;
int n,m,a[M];
int log2[M],min_height[M][18];
long long ans;
namespace Suffix_Array{
int sa[M],rank[M],height[M];
int X[M],Y[M],sum[M],temp[M],tot;
void Get_Rank(int n)
{
static pair b[M];
int i;
for(i=1;i<=n;i++)
b[i]=make_pair(a[i],i);
sort(b+1,b+n+1);
for(i=1;i<=n;i++)
{
if( i==1 || b[i].first!=b[i-1].first )
++tot;
rank[b[i].second]=tot;
}
}
void Radix_Sort(int n,int key[],int order[])
{
int i;
for(i=0;i<=n;i++)
sum[i]=0;
for(i=1;i<=n;i++)
sum[key[i]]++;
for(i=1;i<=n;i++)
sum[i]+=sum[i-1];
for(i=n;i;i--)
temp[sum[key[order[i]]]--]=order[i];
for(i=1;i<=n;i++)
order[i]=temp[i];
}
void Get_Height(int n)
{
int i,j,k;
for(i=1;i<=n;i++)
{
if(rank[i]==1) continue;
j=max(height[rank[i-1]]-1,0);
k=sa[rank[i]-1];
while(a[i+j]==a[k+j])
++j;
height[rank[i]]=j;
}
}
void Prefix_Doubling(int n)
{
int i,j;
Get_Rank(n);
for(j=1;j<=n;j<<=1)
{
for(i=1;i<=n;i++)
{
X[i]=rank[i];
Y[i]=i+j>n?0:rank[i+j];
sa[i]=i;
}
Radix_Sort(n,Y,sa);
Radix_Sort(n,X,sa);
for(tot=0,i=1;i<=n;i++)
{
if( i==1 || X[sa[i]]!=X[sa[i-1]] || Y[sa[i]]!=Y[sa[i-1]] )
++tot;
rank[sa[i]]=tot;
}
}
Get_Height(n);
}
}
int Min_Height(int x,int y)
{
if(x>y) swap(x,y);
int len=log2[y-(++x)+1];
return min(min_height[x][len],min_height[y-(1<>n>>m;
memset(a,0xef,sizeof a);
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
for(n--,i=1;i<=n;i++)
a[i]=a[i+1]-a[i];
a[n+1]=19980402;
for(i=n;i;i--)
a[n+n+2-i]=a[i];
Prefix_Doubling(n+n+1);
for(log2[0]=-1,i=1;i<=n+n+1;i++)
log2[i]=log2[i>>1]+1;
for(i=1;i<=n+n+1;i++)
min_height[i][0]=height[i];
for(j=1;j<=log2[n+n+1];j++)
for(i=1;i+(1<=j)
ans+=last+temp-j+1;
last=Min_Height(rank[(n+n+2)-(i+j-1)],rank[(n+n+2)-(i+j+j+m-1)]);
last=min(last,j-1);
}
}
cout<
