Gym - 102028H Can You Solve the Harder Problem? (后缀数组+RMQ+单调栈)

题意：求一个序列中本质不同的连续子序列的最大值之和。

由于要求“本质不同”，所以后缀数组就派上用场了，可以从小到大枚举每个后缀，对于每个sa[i]，从sa[i]+ht[i]开始枚举(ht[0]=0)，这样就能不重复不遗漏地枚举出每一个子串。

但是这样做，最坏情况仍旧是$O(n^2)$的，可能会被卡掉，需要进一步优化。

对于每个sa[i]，设k=sa[i]+ht[i]，则问题转化成了求max(s[sa[i]],s[sa[i]+1],...,s[k])+max(s[sa[i]],s[sa[i]+1],...,s[k+1])+...+max(s[sa[i]],s[sa[i]+1],...,s[n-1])。

可以发现，随着下标的增大，最大值是单调不减的，这启示我们利用单调栈将后缀进行分段，对于每个最大值不同的段求出后缀和，对于每个sa[i]，利用RMQ求出s[sa[i],k]中的最大值mx，然后在单调栈上二分找到第一个大于mx的值的下标，将贡献分成左右两部分相加即可。

一开始可以将初始序列离散化，求出后缀数组后再还原回去，这样复杂度就不依赖于序列元素的大小而只与序列长度有关了，$O(nlogn)$

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int N=2e5+,inf=0x3f3f3f3f;

 int s[N],buf1[N],buf2[N],b[N],nb,c[N],n,sa[N],ht[N],rnk[N],ST[N][],Log[N],sta[N],idx[N],tp;

 ll sum[N];

 void Sort(int* x,int* y,int m) {

     for(int i=; i<m; ++i)c[i]=;

     for(int i=; i<n; ++i)++c[x[i]];

     for(int i=; i<m; ++i)c[i]+=c[i-];

     for(int i=n-; i>=; --i)sa[--c[x[y[i]]]]=y[i];

 }

 void da(int* s,int n,int m=) {

     int *x=buf1,*y=buf2;

     x[n]=y[n]=-;

     for(int i=; i<n; ++i)x[i]=s[i],y[i]=i;

     Sort(x,y,m);

     for(int k=; k<n; k<<=) {

         int p=;

         for(int i=n-k; i<n; ++i)y[p++]=i;

         for(int i=; i<n; ++i)if(sa[i]>=k)y[p++]=sa[i]-k;

         Sort(x,y,m),p=,y[sa[]]=;

         for(int i=; i<n; ++i)y[sa[i]]=x[sa[i-]]==x[sa[i]]&&x[sa[i-]+k]==x[sa[i]+k]?p-:p++;

         if(p==n)break;

         swap(x,y),m=p;

     }

 }

 void getht() {

     for(int i=; i<n; ++i)rnk[sa[i]]=i;

     ht[]=,s[n]=-;

     for(int i=,k=; i<n; ++i) {

         if(k)--k;

         if(!rnk[i])continue;

         for(; s[i+k]==s[sa[rnk[i]-]+k]; ++k);

         ht[rnk[i]]=k;

     }

 }

 void build() {

     for(int i=; i<n; ++i)ST[i][]=s[i];

     for(int k=; k<=Log[n]; ++k)

         for(int i=; i+(<<k)-<n; ++i)

             ST[i][k]=max(ST[i][k-],ST[i+(<<(k-))][k-]);

 }

 int qry(int L,int R) {

     int k=Log[R-L+];

     return max(ST[L][k],ST[R-(<<k)+][k]);

 }

 struct QR {

     int k,mx;

     bool operator<(const QR& b)const {return k<b.k;}

 } qr[N];

 void push(int x,int i) {

     for(; ~tp&&x>=sta[tp]; --tp);

     sta[++tp]=x,sum[tp]=(ll)x*(idx[tp-]-i)+sum[tp-],idx[tp]=i;

 }

 int main() {

     Log[]=-;

     for(int i=; i<N; ++i)Log[i]=Log[i>>]+;

     int T;

     for(scanf("%d",&T); T--;) {

         scanf("%d",&n);

         for(int i=; i<n; ++i)scanf("%d",&s[i]);

         nb=;

         for(int i=; i<n; ++i)b[nb++]=s[i];

         sort(b,b+nb),nb=unique(b,b+nb)-b;

         for(int i=; i<n; ++i)s[i]=lower_bound(b,b+nb,s[i])-b;

         da(s,n,n+),getht();

         for(int i=; i<n; ++i)s[i]=b[s[i]];

         build();

         ll ans=;

         for(int i=; i<n; ++i) {

             int k=sa[i]+ht[i];

             qr[i]= {k,qry(sa[i],k)};

         }

         sort(qr,qr+n);

         sta[tp=]=inf,sum[tp]=,idx[tp]=n;

         for(int i=n-,j=n-; i>=; --i) {

             int k=qr[i].k,mx=qr[i].mx;

             for(; j>=k; --j)push(s[j],j);

             int t=lower_bound(sta,sta+tp+,mx,greater<int>())-sta-;

             ans+=(ll)mx*(idx[t]-k)+sum[t];

         }

         printf("%lld\n",ans);

     }

     return ;

 }

巴特西

Gym - 102028H Can You Solve the Harder Problem? (后缀数组+RMQ+单调栈)

最新文章

热门文章