997E - Good Subsegments - CodeForces Solution

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define int ll
const int N = 120000 + 7;
int n, a[N], q, ret[N];
vector<pair<int, int>> queries[N];

int sol[4 * N];
int mn[4 * N];
int lazy[4 * N];
int cnt[4 * N];
int coef[4 * N];

void build(int v, int tl, int tr) {
  mn[v] = tl;
  cnt[v] = 1;
  if (tl < tr) {
    int tm = (tl + tr) / 2;
    build(2 * v, tl, tm);
    build(2 * v + 1, tm + 1, tr);
  }
}

void join(int v) {
  sol[v] = sol[2 * v] + sol[2 * v + 1];
  mn[v] = min(mn[2 * v], mn[2 * v + 1]);
  cnt[v] = cnt[2 * v] * (mn[2 * v] == mn[v]) + cnt[2 * v + 1] * (mn[2 * v + 1] == mn[v]);
}

void push(int v, int tl, int tr) {
  assert(tl < tr);
  if (lazy[v]) {
    if (tl < tr) {
      mn[2 * v] += lazy[v];
      mn[2 * v + 1] += lazy[v];
      lazy[2 * v] += lazy[v];
      lazy[2 * v + 1] += lazy[v];
    }
    lazy[v] = 0;
  }
  if (coef[v]) {
    if (tl < tr) {
      if (mn[2 * v] == mn[v]) {
        sol[2 * v] += coef[v] * cnt[2 * v];
        coef[2 * v] += coef[v];
      }
      if (mn[2 * v + 1] == mn[v]) {
        sol[2 * v + 1] += coef[v] * cnt[2 * v + 1];
        coef[2 * v + 1] += coef[v];
      }
    }
    coef[v] = 0;
  }
}

void update(int v, int tl, int tr, int l, int r, int val) {
  if (tr < l || r < tl) return;
  if (l <= tl && tr <= r) {
    mn[v] += val;
    lazy[v] += val;
    return;
  }
  push(v, tl, tr);
  int tm = (tl + tr) / 2;
  update(2 * v, tl, tm, l, r, val);
  update(2 * v + 1, tm + 1, tr, l, r, val);
  join(v);
}

int query(int v, int tl, int tr, int l, int r) {
  if (tr < l || r < tl) {
    return 0;
  }
  if (l <= tl && tr <= r) {
    return sol[v];
  }
  push(v, tl, tr);
  int tm = (tl + tr) / 2;
  return query(2 * v, tl, tm, l, r) + query(2 * v + 1, tm + 1, tr, l, r);
}

signed main() {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

  int n, q;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  build(1, 1, n);
  cin >> q;
  for (int i = 1; i <= q; i++) {
    int l, r;
    cin >> l >> r;
    queries[r].push_back({l, i});
    ret[i] = -1;
  }
  vector<int> smin, smax;
  smin.push_back(0);
  smax.push_back(0);
  update(1, 1, n, 1, n, -1);
  for (int i = 1; i <= n; i++) {
    update(1, 1, n, 1, n, -1);
    while ((int) smax.size() >= 2 && a[i] > a[smax.back()]) {
      int first = smax[(int) smax.size() - 2] + 1;
      int last = smax[(int) smax.size() - 1];
      update(1, 1, n, first, last, a[i] - a[smax.back()]);
      smax.pop_back();
    }
    smax.push_back(i);
    update(1, 1, n, 1, n, -1);
    while ((int) smin.size() >= 2 && a[i] < a[smin.back()]) {
      int first = smin[(int) smin.size() - 2] + 1;
      int last = smin[(int) smin.size() - 1];
      update(1, 1, n, first, last, a[smin.back()] - a[i]);
      smin.pop_back();
    }
    smin.push_back(i);
    coef[1]++;
    sol[1] += cnt[1];
    for (auto &it : queries[i]) {
      int j = it.first, id = it.second;
      ret[id] = query(1, 1, n, j, i);
    }
  }
  for (int i = 1; i <= q; i++) {
    cout << ret[i] << " ";
  }
  return 0;
}