他要求的就是lcp(x,y)>=i的(x,y)的个数和a[x]*a[y]的最大值

做一下后缀和，就只要求lcp=i的了

既然lcp(x,y)=min(h[rank[x]+1],..,[h[rank[y]]])

那么我们求出来对于每一个h，以它作为最小值的区间的左右端点就可以了，这个可以用单调栈，具体做法见(?哪里具体了)

假设L是i左面第一个h小于等于它的，R是i右面第一个小于它的（一定要一边有=一边没有，很关键）

那就相当于lcp(x,y)=h[i] ,rank[x]∈[L,i-1],rank[y]∈[i,R-1]

数量就是这两个区间大小乘一下，最大值是max(最大值之积，最小值之积）（因为会有负的），这个可以用ST表来做

貌似并查集也能做 但我哪会啊

 

写的这么辣鸡 开着O2才勉强水过洛谷 哪敢到bzoj去交啊

upd:(Time Limit: 10 Sec)

1 #include
     
        2 #define pa pair
      
         3 #define CLR(a,x) memset(a,x,sizeof(a))  4 using namespace std;  5 typedef long long ll;  6 const int maxn=3e5+10;  7 const ll inf=1e18;  8   9 inline ll rd(){ 10     ll x=0;char c=getchar();int neg=1; 11     while(c<'0'||c>'9'){
   if(c=='-') neg=-1;c=getchar();} 12     while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar(); 13     return x*neg; 14 } 15  16 int N,M,deli[maxn],sa[maxn<<1],rnk[maxn<<1],rnk1[maxn<<1],tmp[maxn<<1],h[maxn<<1],cnt[maxn]; 17 ll ans2[maxn],ma[maxn][20],mn[maxn][20],dt[maxn]; 18 int stk[maxn],sh,rg[maxn]; 19 char s[maxn]; 20  21 inline void setsa(){ 22     int i,j=0,k; 23     for(i=1;i<=N;i++) cnt[s[i]]=1; 24     for(i=1;i<=M;i++) cnt[i]+=cnt[i-1]; 25     for(i=N;i;i--) rnk[i]=cnt[s[i]]; 26     for(k=1;j!=N;k<<=1){ 27         // printf("%d %d %d\n",M,k,j); 28         CLR(cnt,0); 29         for(i=1;i<=N;i++) cnt[rnk[i+k]]++; 30         for(i=1;i<=M;i++) cnt[i]+=cnt[i-1]; 31         for(i=N;i;i--) tmp[cnt[rnk[i+k]]--]=i; 32         CLR(cnt,0); 33         for(i=1;i<=N;i++) cnt[rnk[i]]++; 34         for(i=1;i<=M;i++) cnt[i]+=cnt[i-1]; 35         for(i=N;i;i--) sa[cnt[rnk[tmp[i]]]--]=tmp[i]; 36         memcpy(rnk1,rnk,sizeof(rnk)); 37         i=2;rnk[sa[1]]=j=1; 38         for(;i<=N;i++){ 39             if(rnk1[sa[i]]!=rnk1[sa[i-1]]||rnk1[sa[i]+k]!=rnk1[sa[i-1]+k]) j++; 40             rnk[sa[i]]=j; 41         }M=j; 42     } 43     for(i=1;i<=N;i++) 44         sa[rnk[i]]=i; 45 } 46 inline void seth(){ 47     for(int i=1,j=0;i<=N;i++){ 48         if(rnk[i]==1) continue; 49         if(j) j--; 50         int x=sa[rnk[i]-1]; 51         while(i+j<=N&&x+j<=N&&s[i+j]==s[x+j]) j++; 52         h[rnk[i]]=j; 53     } 54 } 55  56 inline void setma(){ 57     for(int i=N;i;i--){ 58         ma[i][0]=mn[i][0]=deli[sa[i]]; 59         for(int j=1;i+(1<
       
        <=N;j++){ 60             int k=i+(1<<(j-1)); 61             ma[i][j]=max(ma[i][j-1],ma[k][j-1]); 62             mn[i][j]=min(mn[i][j-1],mn[k][j-1]); 63         } 64     } 65 } 66  67 inline pa getma(int l,int r){ 68     int k=log2(r-l+1); 69     return make_pair(max(ma[l][k],ma[r-(1<
        
         <
         
          h[i]) 75             rg[stk[sh--]]=i; 76         stk[++sh]=i; 77     }while(sh) rg[stk[sh--]]=N+1; 78     for(int i=N;i;i--){ 79         while(sh&&h[stk[sh]]>=h[i]){ 80             int r=rg[stk[sh]]-1; 81             pa x=getma(i,stk[sh]-1),y=getma(stk[sh],r); 82             ans2[h[stk[sh]]]=max(ans2[h[stk[sh]]],max(x.first*y.first,x.second*y.second)); 83             dt[h[stk[sh]]]+=1ll*(stk[sh]-i)*(r-stk[sh]+1); 84             sh--; 85         } 86         stk[++sh]=i; 87     } 88 } 89  90 int main(){ 91     // freopen("testdata.in","r",stdin); 92     // freopen("aa.out","w",stdout); 93     int i,j,k; 94     N=rd(); 95     scanf("%s",s+1); 96     for(i=1;i<=N;i++) 97         deli[i]=rd(); 98     M=127;setsa(); 99     seth();100     setma();101     CLR(ans2,-127);102     solve();103     for(i=N-1;i>=0;i--) dt[i]+=dt[i+1],ans2[i]=max(ans2[i],ans2[i+1]);104     for(i=0;i