Kyselyt

#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
#define F first
#define S second

using namespace std;

const int N=1<<18;
const ll INF=9999999999;

ll sum[201010];
ll lstr[2*N], laz[2*N], matr[2*N];
ll ans[201010];
pair<pair<int,int>,int> query[201010];
ll aa[201010];

ll getSum(int a, int b, int nod, int ast,int bst) {
	if (a>=bst || b<=ast) return 0;
	if (laz[nod]>0) {
		int le = min(b,bst)-max(a,ast);
		return le*laz[nod];
	}
	if (a<=ast && b>=bst) return lstr[nod];
	int midst=(ast+bst)/2;
	return getSum(a,b,2*nod,ast,midst)+getSum(a,b,2*nod+1,midst,bst);
}

ll getSum(int a, int b) {
	return getSum(a,b,1,0,N);
}

void setVal(int a, int b, ll val, int nod, int ast, int bst) {
	if (a>=bst || b<=ast) return;
	if (bst-ast==1) {
		lstr[nod]=val;
		return;
	}
	if (ast>=a && bst<=b) {
		laz[nod]=val;
		lstr[nod]=(bst-ast)*val;
		return;
	}
	int midst=(ast+bst)/2;
	setVal(a,b,val,2*nod,ast,midst);
	setVal(a,b,val,2*nod+1,midst,bst);
	laz[nod]=0;
	lstr[nod]=lstr[2*nod]+lstr[2*nod+1];
}

void setVal(int a, int b, ll val) {
	setVal(a,b,val,1,0,N);
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n,q;
	cin>>n>>q;
	for (int i=0;i<n;i++) cin>>aa[i];
	aa[n]=INF;
	for (int i=0;i<n;i++) {
		sum[i+1]=aa[i]+sum[i];
	}
	for (int i=0;i<q;i++) {
		int a,b;
		cin>>a>>b;
		a--;
		b--;
		query[i]={{-a,b},i};
	}
	sort(query,query+q);
	vector<int> inIn;
	inIn.push_back(n);
	int cur=n;
	for (int i=0;i<q;i++) {
		int a=-query[i].F.F;
		int b=query[i].F.S;
		for (int j=cur-1;j>=a;j--) {
			while (aa[inIn.back()]<=aa[j]) inIn.pop_back();
			inIn.push_back(j);
			int hlp=inIn.size();
			setVal(inIn[hlp-1],inIn[hlp-2],aa[j]);
		}
		cur=a;
		ans[query[i].S]=getSum(a,b+1)-sum[b+1]+sum[a];
	}
	for (int i=0;i<q;i++) cout<<ans[i]<<"\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