Kyselyt

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

typedef long long ll;

ll x[202020], su[202020], p[202020], t[202020][20][3];

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //Älä käytä, jos tehtävä on interaktiivinen!
    ll n, q;
    cin >> n >> q;
    for (int i=1; i<=n; ++i){
        ll a;
        cin >> a;
        x[i]=a;
        su[i] = su[i-1] + x[i];
    }
    //x[n+1]=1e9+1;
    ll a=n;
    for (int i=n; i>=1; --i){
        if (x[i]>x[i+1]){
            a=i;
        }
        p[i]=a;
    }
    set<pair<ll, ll>> s;
    for (int i=1; i<=n; ++i){
        auto it=s.begin();
        while (it->first<x[i] && it!=s.end()){
            int a=it->second;
            t[a][0][1]=i;
            t[a][0][2]=(i-a)*x[a] - (su[i-1] - su[a-1]);
            s.erase(*it);
            it=s.begin();
        }
        if (x[i+1]<x[i]){
            s.insert({x[i], i});
        }
    }
    for (auto u:s){
        int a=u.second;
        t[a][0][1]=n+2;
        t[a][0][2]=(n+1-a)*x[a] - (su[n] - su[a-1]);
    }
    t[n+1][0][1]=n+2;
    t[n+1][0][2]=0;
    for (int i=n; i>=1; --i){
        if (x[i]<=x[i+1]) {
            t[i][0][1]=t[i+1][0][1];
            t[i][0][2]=t[i+1][0][2];
        }
        for (int j=1; j<=19; ++j){
            ll b=t[i][j-1][1];
            if (b==(n+2)){
                t[i][j][1]=n+2;
                t[i][j][2]=t[i][j-1][2];
            }
            else{
                t[i][j][1]=t[b][j-1][1];
                t[i][j][2]=t[i][j-1][2] + t[b][j-1][2];
            }
        }
    }
    for (int i=1; i<=q; ++i){
        ll a, b;
        cin >> a >> b;
        ll ans=0;
        ll c=0;
        while (t[a][c+1][1]<=b) c++;
        while (c>=0){
            if (t[a][c][1]<=b){
                ans+=t[a][c][2];
                a = t[a][c][1];
            }
            c--;
        }
        if (p[a]<b){
            ans+=(b-p[a])*x[p[a]] - (su[b] - su[p[a]]);
        }
        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