Kyselyt

#include <bits/stdc++.h>
using namespace std;
const int N = 1<<18;
long sp[2*N];
void sp_set(int x, long v) {
  x += N;
  sp[x] = v;
  while (x /= 2) {
    sp[x] = sp[2*x]+sp[2*x+1];
  }
}
long sp_get(int a, int b) {
  long res = 0;
  for (a += N, b += N; a <= b; a /= 2, b /= 2) {
    if (a&1) res += sp[a++];
    if (~b&1) res += sp[b--];
  }
  return res;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n, q;
  cin >> n >> q;
  int t[n];
  for (int i = 0; i < n; ++i) cin >> t[i];
  long st[n+1];
  st[0] = 0;
  for (int i = 0; i < n; ++i) {
    st[i+1] = st[i] + t[i];
  }
  vector<pair<int, int>> qat[n];
  long ans[q];
  for (int i = 0; i < q; ++i) {
    int a, b;
    cin >> a >> b;
    a--; b--;
    qat[a].emplace_back(b, i);
    ans[i] = -(st[b+1]-st[a]);
  }
  vector<pair<int, int>> p;
  p.emplace_back(n, 2e9);
  for (int i = n-1; i >= 0; --i) {
    while (p.back().second <= t[i]) {
      p.pop_back();
    }
    long bcst = long(p.back().first-i)*t[i];
    sp_set(p.size(), bcst);
    p.emplace_back(i, t[i]);
    for (auto [b, j] : qat[i]) {
      int x = lower_bound(p.begin(), p.end(), b, [](auto pr, int u) {return pr.first > u;})-p.begin();
      ans[j] += sp_get(x+1, p.size()-1);
      ans[j] += long(b-p[x].first+1)*p[x].second;
    }
  }
  for (int i = 0; i < q; ++i) cout << ans[i] << "\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