Sunset

/**
 *    author:  Atreus
 *    created: 18.01.2019
**/
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int maxn = 1e5 + 10;

int seg[22][maxn];

int answer = 0;
void get(int id, int L, int R, int l, int r, int x, int h = 0){
	if (L == l and R == r){
		int idx = lower_bound(seg[h] + L, seg[h] + R, x) - (seg[h] + L);
		answer += idx;
		return;
	}
	int mid = (L + R) >> 1;
	if (mid > l)
		get(2 * id + 0, L, mid, l, min(mid, r), x, h + 1);
	if (mid < r)
		get(2 * id + 1, mid, R, max(l, mid), r, x, h + 1);
}

int pre[maxn], a[maxn];

void build(int id, int L, int R, int h = 0){
	if (L + 1 == R){
		seg[h][L] = pre[L];
		return;
	}
	int mid = (L + R) >> 1;
	build(2 * id + 0, L, mid, h + 1);
	build(2 * id + 1, mid, R, h + 1);
	for (int i = L; i < R; i++)
		seg[h][i] = seg[h + 1][i];
	sort(seg[h] + L, seg[h] + R);
}

int main(){
	ios_base::sync_with_stdio(false);
	int n, q;
	cin >> n >> q;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	stack <int> s;
	a[0] = 1000 * 1000 * 1000 + 1;
	s.push(0);
	for (int i = 1; i <= n; i++){
		while (a[i] > a[s.top()])
			s.pop();
		pre[i] = s.top();
		s.push(i);
	}
	build(1, 1, n + 1);
	for (int i = 0; i < q; i++){
		int l, r;
		cin >> l >> r;
		answer = 0;
		get(1, 1, n + 1, l, r + 1, l);
		cout << answer << '\n';
	}
}

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