#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
//#define int ll
#define sz(x) ((int)(x).size())
using pii = pair<int,int>;
using tii = tuple<int,int,int>;
using tiii = tuple<int,int,int,int>;
const int nmax = 2e5 + 5;
#define lsb(x) (x & -x)
#define int ll
struct AIB {
int tree[nmax * 2];
int offset, len;
void init(int l, int r) {
offset = -l + 1;
len = r - l + 1;
memset(tree, 0, sizeof(tree[0]) * (len + 1));
}
void upd(int x, int val) {
x += offset;
//cerr << "+ " << x << ' ' << val << '\n';
while(x <= len)
tree[x] += val,
x += lsb(x);
}
int query(int x) {
x += offset;
int sum = 0;
while(x > 0)
sum += tree[x],
x -= lsb(x);
return sum;
}
int query(int l, int r) {
//cerr << l + offset << ' ' << r + offset << '\n';
return query(r) - query(l - 1);
}
};
#undef int
namespace DS {
AIB offset, firstd, secondd;
namespace Updates {
vector<tii> upd;
void push(int x, int val, int l, int r) {
upd.emplace_back(l, val, x);
upd.emplace_back(r + 1, -val, x + (r + 1) - l);
}
void update(int t, int val, int x) {
//cerr << "+ " << t << ' ' << val << ' ' << x << '\n';
int coef = x - t;
offset.upd(coef, -val * t);
firstd.upd(coef, val);
secondd.upd(coef, (-coef) * val);
}
}
namespace Queries {
int side;
vector<tii> qs;
void push(int l, int r, int t) {
qs.emplace_back(t, l, r);
}
ll query(int t, int l, int r) {
auto [right, mid, left] = tii{r, r - t, l - t};
if(side == 1) { // Orizontal \\ partea superioara
//cerr << t << ' ' << l << ' ' << r << '\t' << '*' << (t + 1) << '\n';
return (ll)offset.query(left, mid) + (ll)firstd.query(left, mid) * (t + 1);
}
else if(side == -1) {
if(mid == right) return 0;
mid++;
return (ll)offset.query(mid, right) + (ll)secondd.query(mid, right) + (ll)firstd.query(mid, right) * (right + 1);
}
else if(side == -2) {
mid = l;
return (ll)offset.query(left, mid) + (ll)secondd.query(left, mid) + (ll)firstd.query(left, mid) * mid;
}
assert(false);
return 0;
}
}
using namespace Queries;
using namespace Updates;
void init(int n) {
vector<int> ind(qs.size());
vector<ll> rez(qs.size(), 0);
//side == 1
Queries::side = 1;
//
offset.init(-n - 1, n + 1);
firstd.init(-n - 1, n + 1);
secondd.init(-n - 1, n + 1);
iota(all(ind), 0);
sort(all(ind), [&](int a, int b) { return qs[a] < qs[b]; });
sort(all(upd));
int ptr = 0;
for(auto i : ind) {
auto [t, l, r] = qs[i];
while(ptr < upd.size() && get<0>(upd[ptr]) <= t) {
auto [time, val, poz] = upd[ptr];
Updates::update(time, val, poz);
ptr++;
}
rez[i] = Queries::query(t, l, r);
}
//for(auto x : rez)
//cout << x << ' ';
//cout << '\n';
//side == -1
Queries::side = -1;
//
offset.init(-n - 1, n + 1);
firstd.init(-n - 1, n + 1);
secondd.init(-n - 1, n + 1);
iota(all(ind), 0);
sort(all(ind), [&](int a, int b) { return get<2>(qs[a]) < get<2>(qs[b]); });
sort(all(upd), [&](auto a, auto b) {return get<2>(a) < get<2>(b); });
ptr = 0;
for(auto i : ind) {
auto [t, l, r] = qs[i];
while(ptr < upd.size() && get<2>(upd[ptr]) <= r) {
auto [time, val, poz] = upd[ptr];
Updates::update(time, val, poz);
ptr++;
}
rez[i] += Queries::query(t, l, r);
}
//for(auto x : rez)
//cout << x << ' ';
//cout << '\n';
//side == -2
Queries::side = -2;
//
offset.init(-n - 1, n + 1);
firstd.init(-n - 1, n + 1);
secondd.init(-n - 1, n + 1);
iota(all(ind), 0);
sort(all(ind), [&](int a, int b) { return get<1>(qs[a]) < get<1>(qs[b]); });
sort(all(upd), [&](auto a, auto b) {return get<2>(a) < get<2>(b); });
ptr = 0;
for(auto i : ind) {
auto [t, l, r] = qs[i];
while(ptr < upd.size() && get<2>(upd[ptr]) <= l) {
auto [time, val, poz] = upd[ptr];
Updates::update(time, val, poz);
ptr++;
}
rez[i] -= Queries::query(t, l, r);
}
for(auto x : rez)
cout << x << ' ';
cout << '\n';
return;
}
}
signed main() {
int n, q;
cin >> n >> q;
vector<int> v(n);
for(auto &x : v)
cin >> x;
vector<int> poz, rend;
for(int i = n - 1; i >= 0; i--) {
DS::Updates::push(i, v[i], 0, 0);
int boundary = i;
while(!poz.empty() && v[poz.back()] <= v[i]) {
DS::Updates::push(poz.back(), v[i] - v[poz.back()], poz.back() - i, rend.back() - i);
boundary = rend.back();
poz.pop_back();
rend.pop_back();
}
poz.emplace_back(i);
rend.emplace_back(boundary);
}
for(int i = 0, t, l, r; i < q; i++) {
cin >> t >> l >> r;
--l;
--r;
DS::Queries::push(l, r, t);
}
DS::init(n);
return 0;
}
/**
De-atâtea nopți aud plouând,
Aud materia plângând..
Sînt singur, și mă duce un gând
Spre locuințele lacustre.
Și parcă dorm pe scânduri ude,
În spate mă izbește-un val --
Tresar prin somn și mi se pare
Că n-am tras podul de la mal.
Un gol istoric se întinde,
Pe-același vremuri mă găsesc..
Și simt cum de atâta ploaie
Pilonii grei se prăbușesc.
De-atâtea nopți aud plouând,
Tot tresărind, tot așteptând..
Sînt singur, și mă duce-un gând
Spre locuințele lacustre.
-- George Bacovia, Lacustră
*/
