Auringonlasku

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ld long double
#define N (1<<18)
#define M 1000000007

using namespace std;

int n, q, h[101010], a, b, lah[101010];
vector<int> sp[N*2];
stack<pair<int,int>> stk;

int query(int v, int o) {
	v += N;
	o += N;
	int ret = 0;
	while(v<=o) {
		if(o%2==0) {
			ret += distance(lower_bound(sp[o].begin(), sp[o].end(), a), upper_bound(sp[o].begin(), sp[o].end(), b));/////
			o--;
			}
		if(v%2==1) {
			ret += distance(lower_bound(sp[v].begin(), sp[v].end(), a), upper_bound(sp[v].begin(), sp[v].end(), b));/////
			v++;
			}
		o /= 2;
		v /= 2;
	}
	return ret;
}

void chg(int k, int x) {
	k += N;
	while(k>=1) {
		sp[k].push_back(x);
		k /= 2;
	}
}

int main() {
	cin.tie(0);
	cout.tie(0);
	ios_base::sync_with_stdio(0);
	cin >> n >> q;
	for(int i=1; i<=n; i++) {
		cin >> h[i];
		while(!stk.empty() && stk.top().first < h[i])
			stk.pop();
		if(!stk.empty()) {
			lah[i] = stk.top().second;
		} else {
			lah[i] = 1e9;
		}
		stk.push(make_pair(h[i], i));
		chg(i, lah[i]);
	}
	for(int i=1; i<N*2; i++)
	sort(sp[i].begin(), sp[i].end());
	for(int i=0; i<q; i++) {
		cin >> a >> b;
		cout << b-a+1-query(a,b) << "\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