Kyselyt

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

const int NLOG = 18;
const int NMAX = 1 << NLOG;

int n;
int arr[NMAX];
int psum[NMAX];
int dp[2*NMAX][NLOG+1];
int dpmax[2*NMAX][NLOG+1];
int nbigger[NMAX];

int cost(int lvl, int a, int b) {
  return lvl*(b-a+1) - (psum[b+1]-psum[a]);
}

int step(int& lvl, int& i, int b) {
  if (lvl == arr[i]) {
    int l = 1;
    while (l < NLOG && i+(1<<l) <= b) l++;
    l--;
    int ans = dp[i][l];
    lvl = dpmax[i][l];
    i += 1<<l;
    lvl = max(lvl, arr[i]);
    return ans;
  }
  int j = nbigger[i];
  int ans = cost(lvl, i, min(b, j-1));
  i = j;
  lvl = max(lvl, arr[i]);
  return ans;
}

int query_step(int a, int b, int lvl) {
  b = min(b, n);
  lvl = max(lvl, arr[a]);
  int ans = 0;
  for (int i=a; i<=b;) {
    ans += step(lvl, i, b);
  }
  return ans;
}

int query(int a, int b) {
  return query_step(a, b, arr[a]);
}

void init() {
  for (int i=0; i<n; i++) {
    psum[i+1] = psum[i] + arr[i];
  }
  vector<int> s;
  s.push_back(n);
  for (int i=n-1; i>=0; i--) {
    while (arr[i] > arr[s.back()]) s.pop_back();
    nbigger[i] = s.back();
    s.push_back(i);
  }
  for (int i=0; i<n; i++) {
    dp[i][0] = 0;
    dpmax[i][0] = arr[i];
  }
  for (int l=1; l<NLOG; l++) {
    for (int i=0; i<n; i++) {
      int i2 = min(n, i + (1<<(l-1)));
      dpmax[i][l] = max(dpmax[i][l-1], dpmax[i2][l-1]);
      int lvl = dpmax[i][l-1];
      int i3 = min(n, i2 + (i2-i));
      dp[i][l] = dp[i][l-1] + query_step(i2, i3-1, lvl);
    }
  }
}

signed main() {
  ios::sync_with_stdio(0);
  int q;
  cin >> n >> q;
  for (int i=0; i<n; i++) {
    cin >> arr[i];
  }
  arr[n] = 1 + *max_element(arr, arr+n);
  init();
  for (int i=0; i<q; i++) {
    int a, b;
    cin >> a >> b, a--, b--;
    if (a > b) swap(a, b);
    cout << query(a, b) << '\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