Sunset

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <cstring>
#include <climits>
#include <iomanip>
#include <bitset>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <list>
#include <map>

using namespace std;

const int N = 200005;

int n, q;
int arr[N];
int ans[N];
int fenw[N];
pair <int, int> p[N];
vector <int> vec[N];
vector <pair<int,int>> e[N];
stack <pair<int,int>> s;

void update(int i, int val) {
  for (; i < N; i += i & (-i)) {
    fenw[i] += val;
  }
}

int query(int i) {
  int ans = 0;
  for (; i > 0; i -= i & (-i)) {
    ans += fenw[i];
  }
  return ans;
}

int query(int x, int y) {
  return (query(y) - (x > 1 ? query(x - 1) : 0));
}

int main() {
  cin >> n >> q;
  for (int i = 1; i <= n; i++) {
    cin >> arr[i];
  }
  for (int i = 1; i <= n; i++) {
    while (!s.empty() && s.top().first < arr[i]) s.pop();
    if (s.empty()) {
      p[i] = make_pair(1, i);
    } else {
      p[i] = make_pair(s.top().second + 1, i);
    }
    s.push({arr[i], i});
  }
  for (int i = 1; i <= n; i++) {
    int x = p[i].first, y = p[i].second;
    vec[x].push_back(y);
    vec[y].push_back(-1);
  }
  for (int i = 0; i < q; i++) {
    int x, y;
    cin >> x >> y;
    e[x].push_back({y, i});
  }
  for (int i = 1; i <= n; i++) {
    for (int x : vec[i]) {
      if (x != -1) {
        update(x, 1);
      }
    }
    for (auto it : e[i]) {
      ans[it.second] = query(i, it.first);
    }
    for (int x : vec[i]) {
      if (x == -1) {
        update(i, -1);
      }
    }
  }
  for (int i = 0; i < q; i++) {
    cout << ans[i] << endl;
  }
  return 0;
}

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 1

Verdict: ACCEPTED

Test 3

Group: 1

Verdict: ACCEPTED

Test 4

Group: 1

Verdict: ACCEPTED

Test 5

Group: 1

Verdict: ACCEPTED

Test 6

Group: 1

Verdict: ACCEPTED

Test 7

Group: 1

Verdict: ACCEPTED

Test 8

Group: 1

Verdict: ACCEPTED

Test 9

Group: 1

Verdict: ACCEPTED

Test 10

Group: 1

Verdict: ACCEPTED

Test 11

Group: 1

Verdict: ACCEPTED

Test 12

Group: 1

Verdict: ACCEPTED

Test 13

Group: 1

Verdict: ACCEPTED

Test 14

Group: 1

Verdict: ACCEPTED

Test 15

Group: 1

Verdict: ACCEPTED

Test 16

Group: 1

Verdict: ACCEPTED

Test 17

Group: 1

Verdict: ACCEPTED

Test 18

Group: 2

Verdict: ACCEPTED

Test 19

Group: 2

Verdict: ACCEPTED

Test 20

Group: 2

Verdict: ACCEPTED

Test 21

Group: 2

Verdict: ACCEPTED

Test 22

Group: 2

Verdict: ACCEPTED

Test 23

Group: 2

Verdict: ACCEPTED

Test 24

Group: 2

Verdict: ACCEPTED

Test 25

Group: 2

Verdict: ACCEPTED

Test 26

Group: 2

Verdict: ACCEPTED

Test 27

Group: 2

Verdict: ACCEPTED

Test 28

Group: 2

Verdict: ACCEPTED

Test 29

Group: 2

Verdict: ACCEPTED

Test 30

Group: 2

Verdict: ACCEPTED

Test 31

Group: 2

Verdict: ACCEPTED

Test 32

Group: 3

Verdict: ACCEPTED

Test 33

Group: 3

Verdict: ACCEPTED

Test 34

Group: 3

Verdict: ACCEPTED

Test 35

Group: 3

Verdict: ACCEPTED

Test 36

Group: 3

Verdict: ACCEPTED

Test 37

Group: 3

Verdict: ACCEPTED

Test 38

Group: 3

Verdict: ACCEPTED

Test 39

Group: 3

Verdict: ACCEPTED

Test 40

Group: 3

Verdict: ACCEPTED

Test 41

Group: 3

Verdict: ACCEPTED

Test 42

Group: 3

Verdict: ACCEPTED

Test 43

Group: 3

Verdict: ACCEPTED

Test 44

Group: 3

Verdict: ACCEPTED

Test 45

Group: 3

Verdict: ACCEPTED

Test 46

Group: 3

Verdict: ACCEPTED

Test 47

Group: 3

Verdict: ACCEPTED

Test 48

Group: 3

Verdict: ACCEPTED

Test 49

Group: 3

Verdict: ACCEPTED

Test 50

Group: 3

Verdict: ACCEPTED

Test 51

Group: 3

Verdict: ACCEPTED

Test 52

Group: 3

Verdict: ACCEPTED

Test 53

Group: 3

Verdict: ACCEPTED

Test 54

Group: 3

Verdict: ACCEPTED