BZOJ2119:股市的预测 分治+后缀数组
Jan 23, 2015 04:33:41 PM
思路:
一种分治的神做法.建议去看原论文[2011年集训队作业]
#include<map> #include<cstdio> #include<cctype> #include<cstring> #include<iostream> #include<algorithm> using namespace std; #define INF 0x3f3f3f3f #define N 50010 int n,lim; int len[N]; inline void pre(int n){ for(int i=2;i<=n;++i)len[i]=len[i>>1]+1; } int Read[N],s[N],ss[N],v[N],nv[N],q[N],c[N]; inline bool cmp(int x,int y,int hl,int n){ return v[x]==v[y]&&((x+hl>n&&y+hl>n)||(x+hl<=n&&y+hl<=n&&v[x+hl]==v[y+hl])); } struct SuffixArray{ int rk[N],h[N],sa[N],rmqh[N][16]; inline void Init(int s[],int n,int m){ int i,j,k,hl,id; for(i=1;i<=m;++i)c[i]=0; for(i=1;i<=n;++i)++c[v[i]=s[i]]; for(i=2;i<=m;++i)c[i]+=c[i-1]; for(i=n;i>=1;--i)sa[c[v[i]]--]=i; for(int d=1;;++d){ for(hl=1<<(d-1),id=0,i=n-hl+1;i<=n;++i)q[++id]=i; for(i=1;i<=n;++i)if(sa[i]>hl)q[++id]=sa[i]-hl; for(i=1;i<=m;++i)c[i]=0; for(i=1;i<=n;++i)++c[v[q[i]]]; for(i=2;i<=m;++i)c[i]+=c[i-1]; for(i=n;i>=1;--i)sa[c[v[q[i]]]--]=q[i]; for(i=m=1;i<=n;++m,i=j+1){ for(j=i;j!=n&&cmp(sa[j],sa[j+1],hl,n);++j); for(k=i;k<=j;++k)nv[sa[k]]=m; } if(--m==n)break; for(i=1;i<=n;++i)v[i]=nv[i]; } for(i=1;i<=n;++i)rk[sa[i]]=i; for(i=1;i<=n;++i){ if(rk[i]==1)continue; j=max(0,h[rk[i-1]]-1); while(i+j<=n&&sa[rk[i]-1]+j<=n&&s[i+j]==s[sa[rk[i]-1]+j])++j; h[rk[i]]=j; } for(i=1;i<=n;++i)rmqh[i][0]=h[i]; for(j=1;j<=15;++j)for(i=1;i+(1<<j)-1<=n;++i)rmqh[i][j]=min(rmqh[i][j-1],rmqh[i+(1<<(j-1))][j-1]); } inline int askrmq(int l,int r){ return min(rmqh[l][len[r-l+1]],rmqh[r-(1<<len[r-l+1])+1][len[r-l+1]]); } inline int getlcp(int x,int y){ int lins=min(rk[x],rk[y]),rins=max(rk[x],rk[y]); if(lins==rins)return n-x+1; else return askrmq(lins+1,rins); } }Steins,revSteins; inline int lcp(int x,int y){ return Steins.getlcp(x,y); } inline int lcs(int x,int y){ return revSteins.getlcp(n-x+1,n-y+1); } inline bool same(int l1,int l2,int len){ return lcp(l1,l2)>=len; } map<int,int>M;int sav[N]; long long res; inline void SteinsGate(int l,int r){ if(r-l+1<lim+2)return; int mid=(l+r)>>1; SteinsGate(l,mid),SteinsGate(mid+1,r); int prelen,suflen,insl,insr,nowlen; for(prelen=0;prelen<lim;++prelen){ suflen=lim-1-prelen; insl=mid-prelen,insr=mid+suflen; if(insl>=l&&insr<=r) for(nowlen=1;insl-nowlen>=l&&insr+nowlen<=r;++nowlen)if(same(insl-nowlen,insr+1,nowlen))++res; } int lins,rins,anotherins,Lcp,Lcs,up,down; for(anotherins=l;anotherins<=r;++anotherins){ if((anotherins>mid&&anotherins-mid-1>=lim)||(mid>anotherins&&mid-anotherins-1>=lim)){ lins=min(mid,anotherins),rins=max(mid,anotherins); Lcp=lcp(lins,rins),Lcs=lcs(lins,rins); down=-INF,up=INF; down=max(down,rins-Lcs-lim+1);//rins-(x+m-1)<=lcs up=min(up,lins+Lcp);//x-lins<=lcp down=max(down,l-lim+rins-lins);//lins-(rins-(x+m-1))+1>=l up=min(up,r+1+lins-rins);//rins+(x-lins)-1<=r down=max(down,lins+1),up=min(up,rins-1);//lins<=x<=rins down=max(down,lins+2-lim),up=min(up,rins-lim);//lins<=x+m-1<=rins if(down<=up){ res+=up-down+1; if(anotherins<mid&&down==anotherins+1)--res; } } } } int main(){ #ifndef ONLINE_JUDGE freopen("tt.in","r",stdin); #endif scanf("%d%d",&n,&lim);register int i; for(i=0;i<n;++i)scanf("%d",&Read[i]); for(--n,i=1;i<=n;++i)s[i]=Read[i]-Read[i-1]; for(i=1;i<=n;++i)sav[i]=s[i];sort(sav+1,sav+n+1); int id=0;for(sav[0]=-INF,i=1;i<=n;++i)if(sav[i]!=sav[i-1])M[sav[i]]=++id; for(i=1;i<=n;++i)s[i]=M[s[i]]; for(i=n;i>=1;--i)ss[i]=s[n+1-i]; pre(n),Steins.Init(s,n,id),revSteins.Init(ss,n,id); SteinsGate(1,n); cout<<res<<endl; return 0; }