Kyselyt

#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
typedef long long ll;

ll a[202020];
ll st[202020];
int ne[202020][19];
ll st2[202020];

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n,q;
	cin>>n>>q;
	for (int i=1;i<=n;i++){
		cin>>a[i];
		st2[i]=st2[i-1]+a[i];
	}
	a[n+1]=1e9+10;
	for (int j=0;j<19;j++){
		ne[n+1][j]=n+1;
	}
	vector<pair<int, int>> x;
	x.push_back({n+1, a[n+1]});
	for (int i=n;i>=1;i--){
		while(x.back().S <= a[i]){
			x.pop_back();
		}
		assert(!x.empty());
		ne[i][0]=x.back().F;
		for (int j=1;j<19;j++){
			ne[i][j]=ne[ne[i][j-1]][j-1];
		}
		st[i]=a[i]*(ll)(ne[i][0]-i)+st[ne[i][0]];
		x.push_back({i, a[i]});
	}
	for (int i=0;i<q;i++){
		int l,r;
		cin>>l>>r;
		ll ans=st[l];
		int d=l;
		for (int j=18;j>=0;j--){
			while (ne[d][j]<=r){
				d=ne[d][j];
			}
		}
		assert(d>=l&&a[d]>=a[l]&&d<=r);
		ans-=st[d];
		ans+=(ll)(r-d+1)*a[d];
		ans-=st2[r]-st2[l-1];
		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