CF 631 E - Product Sum

問題

Problem - E - Codeforces

問題概要

長さの1-indexedな配列がある。この数列に対して一度だけ、数列のある要素を選び、その要素を数列内の好きな位置に移動するという操作をすることができる。

このとき、の取りうる最大値を求めよ。

• 
• 

アイデア

何も動かさなかったときのの値をとして、動かしたときの差分について考える。 以下、2つの場合について考える。

ある要素を右に動かす場合

番目の要素を、番目の要素となるように動かすとする()。 このとき、操作前と操作後でindexはこのようになる。

よって、indexからまでのの和をとすると、

となり、これはCHTを利用し、を減らしていきながら探索することでで探索することができる(傾きには単調性がある方向で追加している)。

ある要素を左に動かす場合

番目の要素を、番目の要素となるように動かすとする()。

これも同様に計算すると、となり、今度はを基準にすることで同様に探索ができる。

実装(C++)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

using P = pair<ll,ll>;
struct CHTrick{
    deque<P> lines;
    bool isMonoticX = false;
    CHTrick(bool flag=false){
        isMonoticX = flag;
    }
    // check whether line l2 is useless
    // maybe overflow
    bool check(P l1, P l2, P l3){
        return (long double)(l3.second-l2.second)*(l2.first-l1.first) >= (long double)(l2.second-l1.second)*(l3.first-l2.first);
    }
    // add line(y=ax+b)
    void add(ll a, ll b){
        if(lines.size()>0 && lines.back().first==a){
            // for maximum val, replace min to max
            b = max(b, lines.back().second);
            lines.pop_back();
        }
        P line(a,b);
        while(lines.size()>=2 && check(*(lines.end()-2),lines.back(),line)){
            lines.pop_back();
        }
        lines.push_back(line);
    }
    // return the value of f_i(x)
    ll f(int i, ll x){
        return lines[i].first*x + lines[i].second;
    }
    ll f(P line, ll x){
        return line.first*x + line.second;
    }
    // minimum -> (lv>=rv), maximum ->(lv<=rv)
    bool comp(ll lv, ll rv){
        return lv <= rv;
    }
    // return the minimum(maximum) values among lines
    ll get(ll x){
        if(isMonoticX){
            while(lines.size()>=2 && comp(f(0,x),f(1,x))){
                lines.pop_front();
            }
            return f(0,x);
        }else{
            int low = -1, high = lines.size()-1;
            while(high-low>1){
                int mid=(high+low)/2;
                if(comp(f(mid,x),f(mid+1,x))) low = mid;
                else high = mid;
            }
            return f(high,x);
        }
    }
};

int main(){
    int n;
    scanf(" %d", &n);
    vector<ll> a(n+1);
    rep(i,n) scanf(" %lld", &a[i+1]);

    vector<ll> sum(a);
    rep(i,n) sum[i+1] += sum[i];

    ll c_def = 0;
    for(ll i=1; i<=n; ++i) c_def += a[i]*i;

    ll mx = 0;

    // 追加する直線の傾きを増加方向にするために、傾きだけ-1倍する
    CHTrick mvL;
    mvL.add(-n, -sum[n]);
    for(ll i=n-1; i>0; --i){
        // 投げるクエリも-1倍
        ll v = mvL.get(-a[i]) + sum[i] - a[i]*i;
        mx = max(mx, v);
        mvL.add(-i, -sum[i]);
    }

    CHTrick mvR;
    mvR.add(1, -sum[0]);
    for(ll i=2; i<=n; ++i){
        ll v = mvR.get(a[i]) + sum[i-1] - a[i]*i;
        mx = max(mx, v);
        mvR.add(i, -sum[i-1]);
    }

    printf("%lld\n", c_def + mx);
    return 0;
}