USACO 2021 Plat Jan P2

#include <bits/stdc++.h>
using namespace std;

#define sz(v) (int)v.size()
#define ar array
typedef long long ll;

const int MAXN = 2e5+10, MAXL = 19;
const ll INF = 1e18+10;

int n, m, q, anc[MAXN][MAXL];
ll a[MAXN], opt[MAXN], pre[MAXN];
vector<int> st;

ll sq(ll x){
    return x*x;
}
ll getAns(ll i, int j){ //return ans for row and column, assuming opt[j] and pre[j] is already calculated
    if (j == 0) return a[j]*(i-1);
    if (i < opt[j]){ //deal with this case later
        if (anc[j][0] == -1) return sq(i)*j + getAns(i, 0); //go all the way to the left
        else {
            int c=j;
            for (int k = MAXL-1; k >= 0; k--) if (anc[c][k] != -1 && i < opt[anc[c][k]]) c = anc[c][k];
            c=anc[c][0];
            assert(i >= opt[c]);

            return getAns(i, c)+sq(i)*(j-c);
        }
//      return getAns(i, j-1)+sq(i);
    }
    ll ans=0;
    ans += a[j]*(i-opt[j]);
    ans += pre[j];
    return ans;
}
ll getAnsSlow(ll i, int j){ //return ans for row and column, assuming opt[j] andd pre[j-1] is already calculated
    if (j == 0) return a[j]*(i-1);
    ll ans=0;
    ans += (i-opt[j])*a[j];
    ans += sq(opt[j]);
    ans += getAns(opt[j], j-1);
    return ans;
}
void calc(int j){ //calculate ans s.t. you start at (opt[j], j)

    while (sz(st) && opt[st.back()] > opt[j]) st.pop_back();
    if (sz(st)) anc[j][0]=st.back();
    else anc[j][0]=-1;

    for (int k = 1; k < MAXL; k++) anc[j][k] = (anc[j][k-1] == -1 ? -1 : anc[anc[j][k-1]][k-1]);
    st.push_back(j);

    pre[j] = sq(opt[j])+getAns(opt[j], j-1);
}
int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n >> m;
    for (int i = 0; i < m; i++) cin >> a[i];

    opt[0]=1;
    st.push_back(0);

    for (int i = 1; i < m; i++){

        auto should_dec = [&](ll j) -> bool {
            if (j == 1) return 0;
            opt[i]=j-1;
            ll nc=getAnsSlow(n, i);
            opt[i]=j;
            ll oc=getAnsSlow(n, i);
            return nc <= oc;
        };
        ll lo=0, hi=n+1, mid=(lo+hi)/2;
        while (lo < mid && mid < hi){
            if (!should_dec(mid)) lo=mid;
            else hi=mid;
            mid=(lo+hi)/2;
        }
        opt[i]=mid;


//      ll j=n; //turn left at opt[i]
//      while (j > 1){
//          if (should_dec(j)) j--;
//          else break;
//      }
//      opt[i]=j;

        calc(i);
    }

//  cerr << "opt\n";
//  for (int i = 0; i < n; i++) cerr << opt[i] << ' '; cerr << '\n';

    cin >> q;
    while (q--){
        ll i, j; cin >> i >> j, j--;
        cout << getAns(i, j) << '\n';
    }
}