Kyselyt

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
using namespace std;
typedef long long ll;
const int MN = 2<<17;
ll xs[MN];
ll bit[MN];
void add(int i, ll x) {
	i+=2;
	for(;i<MN;i+=i&-i) bit[i]+=x;
}
ll get(int i) {
	i+=2;
	ll r=0;
	for(;i;i&=i-1) r+=bit[i];
	return r;
}
struct Q {
	int i, a, b;
	bool operator<(const Q& q) const {
		return b<q.b;
	}
};
Q qs[MN];
 
struct S {
	int i;
	ll v;
};
 
ll sums[MN];
ll res[MN];
 
int main() {
	int n,q;
	cin>>n>>q;
	for(int i=0; i<n; ++i) cin>>xs[i],sums[i+1]=sums[i]+xs[i];
	for(int i=0; i<q; ++i) {
		int a,b;
		cin>>a>>b;
		qs[i] = {i,a-1,b-1};
	}
	sort(qs,qs+q);
	vector<S> st;
	st.push_back({-1,1LL<<30});
	for(int i=0,qi=0; i<n; ++i) {
		ll x = xs[i];
		while(x >= st.back().v) {
			S s = st.back();
			st.pop_back();
			add(st.back().i+1, s.v*(i-s.i));
			add(s.i+1, -s.v*(i-s.i));
		}
		if (x < st.back().v) {
			st.push_back({i,x});
		}
		for(; qi<q && qs[qi].b == i; ++qi) {
			int a=qs[qi].a, b=qs[qi].b;
			auto it = partition_point(st.begin(), st.end(), [a](const S& s){return s.i < a;});
			res[qs[qi].i] = get(a) + it->v * (b-it->i+1) - (sums[b+1]-sums[a]);
		}
	}
	copy(res,res+q,ostream_iterator<ll>(cout,"\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