首页 > 代码库 > 【BZOJ】【3238】【AHOI2013】diff(差异)

【BZOJ】【3238】【AHOI2013】diff(差异)

题目链接:www.lydsy.com/JudgeOnline/problem.php?id=3238

后缀数组

  这题题面给的暗示性就很强啊……一看就是要用后缀xx一家的算法,由于本蒻只会后缀数组所以就拿后缀数组写了。

  

  这个题目的要求……我们很明显可以直接预处理出来T(i)+T(j)的总和,为n*(n-1)*(n+1)/2。(应该挺容易推的吧?自己画一下(样例):当i为1的时候,j可以为2、3、4、5。则1算了4次,2~5各一次;然后2算三次,3~5算一次;3算两次,4、5算一次;4算一次,5算1次。总共加起来,每个数各算了4次。1~5的和是n*(n+1)/2,总共算了(n-1)次,再乘一下就行了。)

  难点在于LCP的减……这个地方我们可以直接在height数组上搞,我们可以发现,每一对(i,j)都对应了height数组上的一段区间、甚至是点!(当i,j两个子串rank相连的时候)那么同样的,每一个height数组上的一段区间(点)也对应我们要求的一个LCP。

  这样有什么好处呢?原本暴力的做法是枚举i,j,用RMQ算LCP,再减;而现在我们转换成直接算LCP,而不用考虑是谁和谁的LCP(事实上并不会落下任何一个),这样问题就简单多了:利用求LCP的特殊性,我们对于每一个height[i],都能找到一段区间[l,r],使得height[i]=min(height[l]~height[r])。额意思就是 i 是[l,r]这个区间上的最小值。这样LCP=height[i]的对数为 (l-i+1)*(r-i+1) 【ps.我们事先说过,[i,i]这样的一个点也算】也就是说我们的答案里可以减去 2*height[i]*(l-i+1)*(r-i+1) 这样一个值。

  但是!!这样会有重复计算的情况:

    举个栗子:height为 1 2 3 1 2 1 1时,第一个2的[l,r]区间为[1,7],第二个为[1,7],明显有重复计算了([l,i] 和 [i,r]这两段有重叠,也就是计算了两次)所以我们在计算对于每个 i 所能到达的[l,r]区间时,遇到相等元素,必须分开处理:比如如果向右遇到相等元素则可以继续扩展,而向左遇到则停止。

  

  现在分析清楚了,最后的问题是:怎么算l[i],r[i],也就是每个height[i]对应的区间?

  这里我们可以利用一个叫做单调栈的东西,维护栈里的元素height[j]都比当前的height[j]要小,如果大则弹出,这样就能O(N)求出所有的l[i],r[i]了。

 

错误:1.计算答案的时候,必须要在乘法中加上 (LL)类型强制转换,否则会出错。

   2.在栈为空的时候,意味着左边(右边)所有的元素都比当前的要大,则范围应为从端点(1或n)到i的整个区间,而不是i  (见代码)

技术分享
  1 /**************************************************************  2     Problem: 3238  3     User: ProgrammingApe  4     Language: C++  5     Result: Accepted  6     Time:3416 ms  7     Memory:23244 kb  8 ****************************************************************/  9   10 //练习六 T1 闫鸿宇 11 //BZOJ 3238 12 #include<cmath> 13 #include<cstdio> 14 #include<cstring> 15 #include<cstdlib> 16 #include<iostream> 17 #include<algorithm> 18 #define rep(i,n) for(int i=0;i<n;++i) 19 #define F(i,j,n) for(int i=j;i<=n;++i) 20 #define D(i,j,n) for(int i=j;i>=n;--i) 21 using namespace std; 22 const int N=500010; 23 typedef long long LL; 24 //#define debug 25 int n,m,sa[N],c[N],wa[N],wb[N],wv[N],rank[N],height[N],l[N],r[N]; 26   27 int cmp(int *r,int a,int b,int l){ 28     return r[a]==r[b] && r[a+l]==r[b+l]; 29 } 30   31 void DA(char *s,int *sa,int n,int m){ 32     int i,j,p,*x=wa,*y=wb; 33     rep(i,m) c[i]=0; 34     rep(i,n) c[x[i]=s[i]]++; 35     F(i,1,m-1) c[i]+=c[i-1]; 36     D(i,n-1,0) sa[--c[x[i]]]=i; 37     for(p=0,j=1;p<n;j<<=1,m=p){ 38         for(p=0,i=n-j;i<n;++i) y[p++]=i; 39         rep(i,n) if (sa[i]>=j) y[p++]=sa[i]-j; 40           41         rep(i,m) c[i]=0; 42         rep(i,n) c[x[y[i]]]++; 43         F(i,1,m-1) c[i]+=c[i-1]; 44         D(i,n-1,0) sa[--c[x[y[i]]]]=y[i]; 45         swap(x,y); p=1; x[sa[0]]=0; 46         F(i,1,n-1) x[sa[i]]=cmp(y,sa[i-1],sa[i],j) ? p-1 : p++; 47     } 48 } 49   50 void calheight(char *s,int *sa,int n){ 51     int k=0; 52     F(i,1,n) rank[sa[i]]=i; 53     rep(i,n){ 54         if (k) k--; 55         int j=sa[rank[i]-1]; 56         while(s[i+k]==s[j+k]) k++; 57         height[rank[i]]=k; 58     } 59 } 60   61 int q[N],st[N],top=0; 62 char s[N]; 63 int main(){ 64 //  freopen("input.txt","r",stdin); 65 //  freopen("output.txt","w",stdout); 66     scanf("%s",&s); 67     int n=strlen(s); 68     rep(i,n) s[i]=s[i]-a+2; 69     s[n]=0; 70       71     DA(s,sa,n+1,30); 72     calheight(s,sa,n); 73     height[1]=height[n+1]=0; 74   75     LL ans=(LL)((LL)n*(n-1)*(n+1))/2,delta=0;   76     //T(i) 和 T(j) 的总和 77       78     top=0; 79     st[top++]=1; 80     F(i,1,n){ 81         while (top && height[st[top-1]] > height[i]) top--; 82         if (top) l[i]=st[top-1]+1; 83         else l[i]=1; 84         st[top++]=i; 85     } 86       87     top=0; 88     st[top++]=n; r[n]=n; 89     D(i,n,1){ 90         while (top && height[st[top-1]] >= height[i]) top--; 91         if (top) r[i]=st[top-1]-1; 92         else r[i]=n;//!!!! 93         st[top++]=i; 94     } 95       96     #ifdef debug 97     F(i,1,n) printf("%d ",height[i]); 98     printf("\n"); 99     F(i,1,n) printf("%d ",l[i]);100     printf("\n");101     F(i,1,n) printf("%d ",r[i]);102     printf("\n");103     #endif104     F(i,2,n){105         delta+=(LL)2*(LL)height[i]*(LL)(i-l[i]+1)*(LL)(r[i]-i+1);106         #ifdef debug107         printf("%d * %d * %d = %d\n",height[i],i-l[i]+1,r[i]-i+1,height[i]*(i-l[i]+1)*(r[i]-i+1));108         #endif109     }110     #ifdef debug111     printf("%lld %lld\n",ans,delta);112     #endif113     ans-=delta;114     printf("%lld\n",ans);115     return 0;116 }
View Code

 

【BZOJ】【3238】【AHOI2013】diff(差异)