#include <bits/stdc++.h>
#include <immintrin.h>
using namespace std;
using ll = long long;
using ld = long double;
#define x first
#define y second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
mt19937 mt(123);
void solve();
void init();
int32_t main() {
#ifndef LOCAL
cin.tie(nullptr)->sync_with_stdio(false);
#endif
cout << fixed << setprecision(30);
init();
int t = 1;
// cin >> t;
while (t--) {
solve();
}
}
struct segment_tree {
vector<ll> st;
int sz;
segment_tree() = default;
segment_tree(vector<int> a) {
sz = 1;
while (sz < a.size()) {
sz <<= 1;
}
st.resize(2 * sz, 0);
for (int i = 0; i < a.size(); i++) {
st[sz + i] = a[i];
}
for (int i = sz - 1; i > 0; i--) {
st[i] = st[2 * i] + st[2 * i + 1];
}
}
void add(int i, ll x) {
i += sz;
while (i) {
st[i] += x;
i >>= 1;
}
}
ll get(int l, int r) {
l += sz;
r += sz;
ll res = 0;
while (l <= r) {
if (l & 1) {
res += st[l++];
}
if (~r & 1) {
res += st[r--];
}
l >>= 1;
r >>= 1;
}
return res;
}
};
struct mseg_tree {
segment_tree def, step;
int now_step;
mseg_tree() = default;
mseg_tree(int n) {
now_step = 0;
def = segment_tree(vector<int>(n, 0));
step = segment_tree(vector<int>(n, 0));
}
void add_def(int i, int x) {
def.add(i, x);
}
void add_step(int i, int x) {
step.add(i, x);
def.add(i, -1ll * x * now_step);
}
void next_step() {
now_step++;
}
void set_step(int new_step) {
now_step = new_step;
}
ll get(int l, int r) {
return def.get(l, r) + now_step * step.get(l, r);
}
};
struct sparse_max {
using Type = pair<int, int>;
vector<vector<Type>> sp;
vector<int> p;
sparse_max(const vector<Type>& a) {
int n = a.size(), lg = 1;
while ((1 << lg) < n) {
lg++;
}
sp.resize(lg, vector<Type>(n));
for (int i = 0; i < n; i++) {
sp[0][i] = a[i];
}
for (int l = 1; l < lg; l++) {
for (int i = 0; i <= n - (1 << l); i++) {
sp[l][i] = max(sp[l - 1][i], sp[l - 1][i + (1 << (l - 1))]);
}
}
int nw = 0;
p.resize(n + 1, 0);
for (int i = 1; i <= n; i++) {
if ((1 << nw) * 2 < i) {
nw++;
}
p[i] = nw;
}
}
Type get(int l, int r) {
int lev = p[r - l + 1];
return max(sp[lev][l], sp[lev][r - (1 << lev) + 1]);
}
};
struct sparse_min {
using Type = pair<int, int>;
vector<vector<Type>> sp;
vector<int> p;
sparse_min(const vector<Type>& a) {
int n = a.size(), lg = 1;
while ((1 << lg) < n) {
lg++;
}
sp.resize(lg, vector<Type>(n));
for (int i = 0; i < n; i++) {
sp[0][i] = a[i];
}
for (int l = 1; l < lg; l++) {
for (int i = 0; i <= n - (1 << l); i++) {
sp[l][i] = min(sp[l - 1][i], sp[l - 1][i + (1 << (l - 1))]);
}
}
int nw = 0;
p.resize(n + 1, 0);
for (int i = 1; i <= n; i++) {
if ((1 << nw) * 2 < i) {
nw++;
}
p[i] = nw;
}
}
Type get(int l, int r) {
int lev = p[r - l + 1];
return min(sp[lev][l], sp[lev][r - (1 << lev) + 1]);
}
};
void init() {}
void solve() {
int n, q;
cin >> n >> q;
vector<int> a(n), nxt(n), prv(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
// assert(n == 1);
mseg_tree st(n);
for (int i = 0; i < n; i++) {
st.add_step(i, a[i]);
}
vector<pair<int, int>> stack(1, {INT32_MAX, n});
for (int i = n - 1; i >= 0; i--) {
while (a[i] >= stack.back().x) {
stack.pop_back();
}
nxt[i] = stack.back().y;
stack.emplace_back(a[i], i);
}
stack.clear(); stack.emplace_back(INT32_MAX, -1);
for (int i = 0; i < n; i++) {
while (a[i] > stack.back().x) {
stack.pop_back();
}
prv[i] = stack.back().y;
stack.emplace_back(a[i], i);
}
vector<pair<int, int>> fsp(n);
for (int i = 0; i < n; i++) {
fsp[i] = {a[i], -i};
}
sparse_max sp(fsp);
vector<pair<int, pair<int, int>>> ev;
vector<pair<int, int>> qu;
vector<pair<int, int>> seg(q);
vector<ll> ans(q);
for (int i = 0; i < q; i++) {
int t, l, r;
cin >> t >> l >> r; l--; r--;
qu.emplace_back(t, i);
seg[i] = {l, r};
}
for (int i = 0; i < n; i++) {
ev.emplace_back(nxt[i] - i, make_pair(i, -a[i]));
if (prv[i] != -1) {
ev.emplace_back(i - prv[i], make_pair(i, -a[i]));
ev.emplace_back(nxt[i] - prv[i], make_pair(i, a[i]));
}
}
sort(all(ev));
sort(all(qu));
int ptrev = 0, ptrqu = 0;
for (int t = 0; t <= n; t++) {
while (ptrev < ev.size() && ev[ptrev].x == t) {
st.add_step(ev[ptrev].y.x, ev[ptrev].y.y);
ptrev++;
}
st.next_step();
while (ptrqu < qu.size() && qu[ptrev].x == t) {
int i = qu[ptrqu++].y;
auto [l, r] = seg[i];
r++;
ll lans = 0, rans = 0;
{
auto [mx, mxi] = sp.get(max(0, l - t), l);
mxi *= -1;
lans = st.get(mxi + 1, n - 1);
int lst = min({mxi + t, nxt[mxi] - 1});
lans += 1ll * (lst - l + 1) * mx;
}
if (r < n) {
auto [mx, mxi] = sp.get(max(0, r - t), r);
mxi *= -1;
rans = st.get(mxi + 1, n - 1);
int lst = min(mxi + t, nxt[mxi] - 1);
rans += 1ll * (lst - r + 1) * mx;
}
ans[i] = lans - rans;
}
}
for (ll i : ans) {
cout << i << '\n';
}
}
Compilation message
ho_t5.cpp: In constructor 'segment_tree::segment_tree(std::vector<int>)':
ho_t5.cpp:37:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
37 | while (sz < a.size()) {
| ~~~^~~~~~~~~~
ho_t5.cpp:41:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
41 | for (int i = 0; i < a.size(); i++) {
| ~~^~~~~~~~~~
ho_t5.cpp: In function 'void solve()':
ho_t5.cpp:222:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
222 | while (ptrev < ev.size() && ev[ptrev].x == t) {
| ~~~~~~^~~~~~~~~~~
ho_t5.cpp:227:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
227 | while (ptrqu < qu.size() && qu[ptrev].x == t) {
| ~~~~~~^~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
147 ms |
63864 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
