[Codeforces 631E]Product Sum

Link

Definitions:
$SUM[i]=\sum_{k=1}^{i}A_{k}$

For each element, $A_{i}$, how does the characteristic of the array change if we move $A_{i}$ to position $j$?
It changes $A_{i}(j-i)+SUM[i]-SUM[j]$!

Enumerate $i$ and $j$, we get an $O(N^{2})$ solution.
How to speed up?

Treat $j$ as coordinate $x$.
Then we can treat $SUM[j]$ as a function $f(x)$, $A_{i}*j+SUM[i]-A_{i}*i$ as a line $ax+b$ ($a=A_{i},b=SUM[i]-A_{i}*i$)

What we should find is $\max\{(ax+b)-f(x)\}$, where $f(x)$ is a fixed function, $ax+b$ is a line depend on which $A_{i}$ we choose.

Now we have a new way to enumerate: $x$
Enumerate $x$, and find the line whose $ax+b$ is maximum.
Actually, we can use $deque$ to maintain the $convex\ hull$ of these lines.
For each $x$, we just find the corresponding point on the $convex\ hull$, $(x,y)$, $y$ is what we want to get (maximum $ax+b$).

On this picture, black straight lines are $ax+b$ we want to pick to form the $convex\ hull$, the green one.

How to build the $convex\ null$?
Well, this is a long story... Learn it!
(keywords: $monotone\ queue$,$slope\ optimization$)
(hints: sort the lines by their slopes, $a$)

By enumerating $x$ in increasing order, we can reach linear time complexity with the help of monotonicity of $x$, get the maximum $ax+b$ for every $x$.
Update maximum $ax+b-SUM[x]$, this is how much we can increase the characteristic of the array.
Initial characteristic of the array is $\sum_{i=1}^{N}A_{i}*i$

Time complexity：$O(N\log N)$ (remember that $sorting$ was required)

p.s. Actually, we can avoid $sorting$ to reach $O(N)$, that is, only allow element move toward one direction, then these $ax+b$ become rays (instead of lines), enumerate $x$ in that directions, and dynamic maintain the $convex\ hull$. Please remenber that it's required to do the same thing on another direction.
p.s. For $O(N)$ implementation, you can see this.

code:

#include<cstdio>
#include<cassert>
#include<algorithm>
using namespace std;
typedef long long LL;
void getmax(LL &a,const LL &b){if(b>a)a=b;}
struct Deq
{
    int DATA[200000],L,R;
    void Clear(){L=0,R=-1;}
    void PushBack(const int v){DATA[++R]=v;}
    void PopBack(){R--;}
    void PopFront(){L++;}
    int Front(const int i)const{return DATA[L+i];}
    int Back(const int i)const{return DATA[R-i];}
    int Size()const{return R-L+1;}
}DEQ;
int N;
LL A[200001],SUM[200001];
LL GetA(const int i){return A[i];}
LL GetB(const int i){return SUM[i]-A[i]*i;}
double GetX(const int i1,const int i2){return (double)(GetB(i1)-GetB(i2))/(GetA(i2)-GetA(i1));}
bool NeedPopBack(const int i)
{
    if(DEQ.Size()==0)return false;
    if(GetA(i)==GetA(DEQ.Back(0)))return GetB(i)>=GetB(DEQ.Back(0));
    if(DEQ.Size()==1)return false;
    return GetX(DEQ.Back(0),i)<=GetX(DEQ.Back(1),DEQ.Back(0));
}
void BuildConvexHull()
{
    vector<int>order;
    for(int i=1;i<=N;i++)order.push_back(i);
    sort(order.begin(),order.end(),[](const int a,const int b)->bool{return A[a]<A[b];});
    DEQ.Clear();
    for(const int i:order)
    {
        while(NeedPopBack(i))DEQ.PopBack();
        DEQ.PushBack(i);
    }
}
LL Solve()
{
    LL change=0LL;
    for(int i=0;i<=N;i++)
    {
        while(DEQ.Size()>=2&&GetX(DEQ.Front(0),DEQ.Front(1))<=i)DEQ.PopFront();
//        printf("i=%d,DEQ.Front()=%d,a=%I64d,b=%I64d\n",i,DEQ.Front(0),GetA(DEQ.Front(0)),GetB(DEQ.Front(0)));
        getmax(change,GetA(DEQ.Front(0))*i+GetB(DEQ.Front(0))-SUM[i]);
    }
    LL initial_cost=0LL;
    for(int i=1;i<=N;i++)initial_cost+=A[i]*i;
//    printf("initial_cost=%I64d,change=%I64d\n",initial_cost,change);
    return initial_cost+change;
}
int main()
{
//    freopen("in.txt","r",stdin);
    while(scanf("%d",&N)==1)
    {
        SUM[0]=0LL;
        for(int i=1;i<=N;i++)scanf("%I64d",&A[i]),SUM[i]=SUM[i-1]+A[i];
        BuildConvexHull();
        printf("%I64d\n",Solve());
    }
    return 0;
}