I. Max answer（RMQ预处理前缀和）

题目链接： https://nanti.jisuanke.com/t/38228

题目大意：给你n个数，让你找出一个区间中f的最大值，具体的f计算方法，这段区间的和乘以这段区间的最小值。

具体思路：我们枚举每个位置，对于当前位置的数，通过二分找出这个数作为区间最小值能够到达的最左端和最右端。如果是正数，我们直接a[i]*这段区间和就可以了，因为都是正数。

如果当前的a[i]是负数，对于这个点的右段，我们找出一个前缀和最小的点，然后对于这个点的左端，我们找出一个前缀和最大的，这样就能保证选定的区间是最小的了，负数*负数=正数。

预处理出前缀和在每段区间的最小值，最大值，以及每个区间中a[i]的最小值。

感谢qyn的讲解。

AC代码：

 #include<bits/stdc++.h>

 using namespace std;

 # define inf 0x3f3f3f3f

 # define ll long long

 const int maxn = 5e5+;

 ll dp1[maxn][],dp2[maxn][],dp3[maxn][];

 ll  a[maxn];

 ll  qian[maxn];

 int n;

 void RMQ1()

 {

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

     {

         for(int j=; j<=n; j++)

         {

             if(j+(<<i)-<=n)

             {

                 dp1[j][i]=min(dp1[j][i-],dp1[j+(<<(i-))][i-]);

             }

         }

     }

 }

 void RMQ2()

 {

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

     {

         for(int j=; j<=n; j++)

         {

             if(j+(<<i)-<=n)

             {

                 dp2[j][i]=max(dp2[j][i-],dp2[j+(<<(i-))][i-]);

             }

         }

     }

 }

 void RMQ3()

 {

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

     {

         for(int j=; j<=n; j++)

         {

             if(j+(<<i)-<=n)

             {

                 dp3[j][i]=min(dp3[j][i-],dp3[j+(<<(i-))][i-]);

             }

         }

     }

 }

 bool judge(int l,int r,ll val)

 {

     int k=;

     k=(int)log2((double)(r-l+));

     ll tmp=min(dp1[l][k],dp1[r-(<<k)+][k]);

     return tmp==val;

 }

 int Find_l(int pos)

 {

     int l=,r=pos;

     int ans=pos;

     while(l<=r)

     {

         int mid=(l+r)>>;

         if(judge(mid,pos,a[pos]))

         {

             ans=mid;

             r=mid-;

         }

         else

             l=mid+;

     }

     return ans;

 }

 int Find_r(int pos)

 {

     int l=pos,r=n;

     int ans=pos;

     while(l<=r)

     {

         int mid=(l+r)>>;

         if(judge(pos,mid,a[pos]))

         {

             ans=mid;

             l=mid+;

         }

         else

             r=mid-;

     }

     return ans;

 }

 int get_max(int l,int r)

 {

     int k=;

     k=(int)log2((double)(r-l+));

     ll tmp=max(dp2[l][k],dp2[r-(<<k)+][k]);

     return tmp;

 }

 int get_min(int l,int r)

 {

     int k=;

     k=(int)log2((double)(r-l+));

     ll tmp=min(dp3[l][k],dp3[r-(<<k)+][k]);

     return tmp;

 }

 int main()

 {

     scanf("%d",&n);

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

     {

         scanf("%lld",&a[i]);

         dp1[i][]=a[i];

         qian[i]=qian[i-]+a[i];

         dp2[i][]=dp3[i][]=qian[i];

     }

     RMQ1(); ///  区间最小值，在每一次询问的时候求出最左边的端点和最右边的端点

     RMQ2();///  前缀和最大值

     RMQ3(); /// 前缀和最小值

     ll ans=;

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

     {

         int t1=Find_l(i);

         int t2=Find_r(i);

         if(a[i]>)

             ans=max(ans,(qian[t2]-qian[t1-])*a[i]);

         else

         {

             ans=max(ans,a[i]*(get_min(i,t2)-get_max(t1,i)));

         }

     }

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

     return ;

 }

巴特西

I. Max answer（RMQ预处理前缀和）

最新文章

热门文章