Kyselyt

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <cmath>
//#include "stdlib_printing.hh"

using namespace std;
typedef long long LL;

struct RMQ{ // Range maximum query

    LL inf = 1e18;
    vector<vector<LL> > X; // X[i][j] = argmax v[j..j+2^i)
    vector<LL> v;

    RMQ(const vector<LL>& v) : v(v){
        LL n = v.size();
        for(LL L = 1; L <= n; L *= 2){
            vector<LL> R(n); // R[i] = argmax v[i..i+L)
            if(L == 1){
                for(LL i = 0; i < n; i++) R[i] = i;
            }
            else{
                for(LL i = 0; i < n; i++){
                    LL a = v[X.back()[i]];
                    LL b = (i + L/2 < n) ? v[X.back()[i+L/2]] : -inf;
                    if(a > b) R[i] = X.back()[i];
                    else R[i] = X.back()[i+L/2];
                }
            }
            X.push_back(R);
        }
    }

    LL get(LL l, LL r){
        if(l == r) return l;
        LL p = log2(r-l+1);
        LL L = pow(2,p);
        if(v[X[p][l]] > v[X[p][r-L+1]]) return X[p][l];
        else return X[p][r-L+1];
    }

};

void solve(vector<LL>& v, vector<LL>& S, vector<LL>& C, RMQ& rmq, LL l, LL r){
    LL k = rmq.get(l,r);
    cout << S[l] - S[k] + v[k] * (r-k+1) - (C[r+1] - C[l]) << "\n";
}

int main(int argc, char** argv){
    LL n,q; cin >> n >> q;
    vector<LL> v(n);
    for(LL i = 0; i < n; i++) cin >> v[i];
    vector<LL> C(n+1); // C[i] = sum A[0..)
    for(LL i = 0; i < n; i++) C[i+1] = C[i] + v[i];
    RMQ rmq(v);

    vector<LL> S(n);
    vector<pair<LL, LL> > suf; // Value, run length
    LL sum = 0;
    for(LL i = n-1; i >= 0; i--){
        LL deleted = 0;
        while(suf.size() > 0 && v[i] > suf.back().first){
            sum -= suf.back().first * suf.back().second;
            deleted += suf.back().second;
            suf.pop_back();
        }
        suf.push_back({v[i], deleted+1});
        sum += (deleted+1)*v[i];
        S[i] = sum;
    }

    while(q--){
        LL l,r; cin >> l >> r; l--; r--;
        solve(v,S,C,rmq,l,r);
    }

}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 2, 3

Verdict: ACCEPTED

Test 3

Group: 3

Verdict: ACCEPTED

Test 4

Group: 3

Verdict: ACCEPTED

Test 5

Group: 3

Verdict: ACCEPTED