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

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

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

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

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

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

感谢qyn的讲解。

AC代码：

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 # define inf 0x3f3f3f3f
  4 # define ll long long
  5 const int maxn = 5e5+100;
  6 ll dp1[maxn][21],dp2[maxn][21],dp3[maxn][21];
  7 ll  a[maxn];
  8 ll  qian[maxn];
  9 int n;
 10 void RMQ1()
 11 {
 12     for(int i=1; i<=20; i++)
 13     {
 14         for(int j=1; j<=n; j++)
 15         {
 16             if(j+(1<<i)-1<=n)
 17             {
 18                 dp1[j][i]=min(dp1[j][i-1],dp1[j+(1<<(i-1))][i-1]);
 19             }
 20         }
 21     }
 22 }
 23 void RMQ2()
 24 {
 25     for(int i=1; i<=20; i++)
 26     {
 27         for(int j=1; j<=n; j++)
 28         {
 29             if(j+(1<<i)-1<=n)
 30             {
 31                 dp2[j][i]=max(dp2[j][i-1],dp2[j+(1<<(i-1))][i-1]);
 32             }
 33         }
 34     }
 35 }
 36 void RMQ3()
 37 {
 38     for(int i=1; i<=20; i++)
 39     {
 40         for(int j=1; j<=n; j++)
 41         {
 42             if(j+(1<<i)-1<=n)
 43             {
 44                 dp3[j][i]=min(dp3[j][i-1],dp3[j+(1<<(i-1))][i-1]);
 45             }
 46         }
 47     }
 48 }
 49 bool judge(int l,int r,ll val)
 50 {
 51     int k=0;
 52     k=(int)log2((double)(r-l+1));
 53     ll tmp=min(dp1[l][k],dp1[r-(1<<k)+1][k]);
 54     return tmp==val;
 55 }
 56 int Find_l(int pos)
 57 {
 58     int l=1,r=pos;
 59     int ans=pos;
 60     while(l<=r)
 61     {
 62         int mid=(l+r)>>1;
 63         if(judge(mid,pos,a[pos]))
 64         {
 65             ans=mid;
 66             r=mid-1;
 67         }
 68         else
 69             l=mid+1;
 70     }
 71     return ans;
 72 }
 73 int Find_r(int pos)
 74 {
 75     int l=pos,r=n;
 76     int ans=pos;
 77     while(l<=r)
 78     {
 79         int mid=(l+r)>>1;
 80         if(judge(pos,mid,a[pos]))
 81         {
 82             ans=mid;
 83             l=mid+1;
 84         }
 85         else
 86             r=mid-1;
 87     }
 88     return ans;
 89 }
 90 int get_max(int l,int r)
 91 {
 92     int k=0;
 93     k=(int)log2((double)(r-l+1));
 94     ll tmp=max(dp2[l][k],dp2[r-(1<<k)+1][k]);
 95     return tmp;
 96 }
 97 int get_min(int l,int r)
 98 {
 99     int k=0;
100     k=(int)log2((double)(r-l+1));
101     ll tmp=min(dp3[l][k],dp3[r-(1<<k)+1][k]);
102     return tmp;
103 }
104 int main()
105 {
106     scanf("%d",&n);
107     for(int i=1; i<=n; i++)
108     {
109         scanf("%lld",&a[i]);
110         dp1[i][0]=a[i];
111         qian[i]=qian[i-1]+a[i];
112         dp2[i][0]=dp3[i][0]=qian[i];
113     }
114     RMQ1(); ///  区间最小值，在每一次询问的时候求出最左边的端点和最右边的端点
115     RMQ2();///  前缀和最大值
116     RMQ3(); /// 前缀和最小值
117     ll ans=0;
118     for(int i=1; i<=n; i++)
119     {
120         int t1=Find_l(i);
121         int t2=Find_r(i);
122         if(a[i]>0)
123             ans=max(ans,(qian[t2]-qian[t1-1])*a[i]);
124         else
125         {
126             ans=max(ans,a[i]*(get_min(i,t2)-get_max(t1,i)));
127         }
128     }
129     printf("%lld
",ans);
130     return 0;
131 }