Kyselyt

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
ll prefsum[1000000];
ll x[1000000];
int jump[1000000][20];
ll s[1000000][20];
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n,q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> x[i];
    prefsum[1] = x[1];
    for (int i = 2; i <= n; i++) prefsum[i] = prefsum[i-1] + x[i];
    vector<ll> pino;
    pino.push_back(1);
    for (int i = 2; i <= n; i++) {
        while (pino.size() && x[pino.back()] < x[i]) {
            jump[pino.back()][0] = i;
            s[pino.back()][0] = x[pino.back()]*(i-pino.back()) - (prefsum[i-1]-prefsum[pino.back()-1]);
            pino.pop_back();
        }
        pino.push_back(i);
    }
    while (pino.size()) {
        jump[pino.back()][0] = n+1;
        pino.pop_back();
    }
    for (int j = 0; j <= 18; j++) jump[n+1][j] = n+1;
    for (int j = 1; j <= 18; j++) {
        for (int i = 1; i <= n; i++) {
            if (jump[i][j-1] == n+1) jump[i][j] = n+1;
            else jump[i][j] = jump[jump[i][j-1]][j-1];
            s[i][j] = s[i][j-1] + s[jump[i][j-1]][j-1];
        }
    }
    /*
    cout << endl;
    for (int i = 0; i <= 5; i++) {
        for (int j = 1; j <= 10; j++) {
            cout << jump[j][i] << " ";
        }
        cout << endl;
    }
 
    cout << endl;
    */
    for (int i = 0; i < q; i++) {
        int a,b;
        cin >> a >> b;
        ll ans = 0;
        int ind = a;
        while (ind <= b) {
            int pomppu = 0;
            while (jump[ind][pomppu] <= b) {
                pomppu++;
            }
            if (pomppu == 0) break;
            ans += s[ind][pomppu-1];
            ind = jump[ind][pomppu-1];
        }
        ans += x[ind]*(b-ind) - (prefsum[b] - prefsum[ind]);
        cout << ans << "\n";
    }
}
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

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