Kyselyt

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;

const int N = 2e5 + 5;
const int M = 25;
const int INF = 1e9 + 7;

ll t[N];
ll ne[N];
ll f[N][M];
ll h[N][M];
ll s[N];

int main() {
	iostream::sync_with_stdio(false);
	cin.tie(0);
	int n, Q;
	cin >> n >> Q;
	for(int i = 1; i <= n; ++i) {
		cin >> t[i];
		s[i] = s[i-1] + t[i];
	}
	s[n+1] = s[n];
	stack<int> q;
	ne[n+1] = n+1;
	t[n+1] = INF;
	q.push(n+1);
	for(int i = n; i >= 1; --i) {
		while(t[i] > t[q.top()]) {
			q.pop();
		}
		ne[i] = q.top();
		q.push(i);
	}


	for(int k = 0; k < M; ++k) {
		for(int i = 1; i <= n+1; ++i) {
			if(k == 0) {
				h[i][0] = ne[i];
			} else {
				h[i][k] = h[h[i][k-1]][k-1];
			}
		}
	}
/*
	for(int k = 0; k <= 3; ++k) {
		for(int i = 1; i <= n; ++i) {
			cout << h[i][k] << " ";
		}
		cout << "\n";
	}
	return 0;
*/


	for(int k = 0; k < M; ++k) {
		for(int i = 1; i <= n; ++i) {
			if(k == 0) {
				f[i][0] = t[i] * (ne[i] - i - 1) - (s[ne[i] - 1] - s[i]);
			} else {
				f[i][k] = f[i][k-1] + f[h[i][k-1]][k-1];
			}
		}
	}



	for(int i = 1; i <= Q; ++i) {
		int a, b;
		cin >> a >> b;
		ll ans = 0;
		for(int k = 24; k >= 0; --k) {
			if(h[a][k] > b) continue;
			ans += f[a][k];
			a = h[a][k];
		}
		ans += (b - a)*t[a] - (s[b] - s[a]);
		cout << ans << "\n";
	}

}

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