Kyselyt

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e18;
 
class SegTree {
	private:
		const ll NEUT = 0; 
		vector<ll> seg, tag;
		int h = 1;
 
		// Returns length of interval corresponding to position i
		ll len(int i) { return h >> (31 - __builtin_clz(i)); }
 
		void apply(int i, ll v) {
			seg[i] += v * len(i);
			if (i < h) tag[i] += v;
		}
		void push(int i) {
			if (tag[i] == 0) return;
			apply(2*i, tag[i]);
			apply(2*i+1, tag[i]);
			tag[i] = 0;
		}
		ll combine(ll a, ll b) { return a + b; }
 
		ll recGet(int a, int b, int i, int ia, int ib) {
			if (ib <= a || b <= ia) return NEUT;
			if (a <= ia && ib <= b) return seg[i];
			push(i);
			int im = (ia + ib) >> 1;
			return combine(
				recGet(a, b, 2*i, ia, im),
				recGet(a, b, 2*i+1, im, ib));
		}
		void recApply(int a, int b, ll v, int i, int ia, int ib) {
			if (ib <= a || b <= ia) return;
			if (a <= ia && ib <= b) apply(i, v);
			else {
				push(i);
				int im = (ia + ib) >> 1;
				recApply(a, b, v, 2*i, ia, im);
				recApply(a, b, v, 2*i+1, im, ib);
				seg[i] = combine(seg[2*i], seg[2*i+1]);
			}
		}
	public:
		SegTree(int n) {
			while(h < n) h *= 2;
			seg.resize(2*h, NEUT);
			tag.resize(h, 0);
		}
		ll rangeSum(int a, int b) { return recGet(a, b+1, 1, 0, h); }
		void rangeAdd(int a, int b, ll v) { recApply(a, b+1, v, 1, 0, h); }
};
 
 
void solve() {
	int n, q;
	cin >> n >> q;
	vector<ll> as(n);
	for (ll& a : as) cin >> a;
 
	vector<pair<int, pair<int, int>>> qs(q);
	for (int i = 0; i < q; ++i) {
		int a, b;
		cin >> a >> b;
		qs[i] = {a-1, {b-1, i}};
	}
	sort(qs.begin(), qs.end());
	
	SegTree seg(n);
	vector<ll> res(q, -1);
	vector<pair<ll, int>> stack = {{INF, n}};
	for (int i = n-1; i >= 0; --i) {
		seg.rangeAdd(i, i, 0);
		while(stack.back().first <= as[i]) {
			ll dy = as[i] - stack.back().first;
			int s = stack.back().second;
			stack.pop_back();
 
			int t = stack.back().second;
			seg.rangeAdd(s, t-1, dy);
		}
		stack.emplace_back(as[i], i);
 
		while(q > 0 && qs[q-1].first == i) {
			--q;
			res[qs[q].second.second] = seg.rangeSum(i, qs[q].second.first);
		}
	}
 
	for (auto v : res) cout << v << '\n';
}
 
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
 
	solve();
}

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