#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, q;
cin >> n >> q;
vector<int> s(n);
for (int i = 0; i < n; i++) {
cin >> s[i];
}
vector<int> t(q), l(q), r(q);
for (int i = 0; i < q; i++) {
cin >> t[i] >> l[i] >> r[i];
--l[i]; --r[i];
if (t[i] == n) {
--t[i];
}
}
vector<int> prv(n);
vector<int> stk;
for (int i = 0; i < n; i++) {
while (!stk.empty() && s[i] >= s[stk.back()]) {
stk.pop_back();
}
prv[i] = (stk.empty() ? -1 : stk.back());
stk.push_back(i);
}
vector<vector<int>> ch(n);
for (int i = 0; i < n; i++) {
if (prv[i] != -1) {
ch[prv[i]].push_back(i);
}
}
vector<int> to(n);
for (int i = n - 1; i >= 0; i--) {
to[i] = i;
for (int j : ch[i]) {
to[i] = max(to[i], to[j]);
}
}
vector<long long> res(q);
{
vector<long long> pref(n);
for (int i = 0; i < n; i++) {
if (i > 0) {
pref[i] = pref[i - 1];
}
pref[i] += s[i];
}
for (int i = 0; i < q; i++) {
res[i] = pref[r[i]] - pref[l[i] - 1];
}
}
vector<vector<array<int, 3>>> seg(n);
for (int i = 0; i < n; i++) {
for (int j : ch[i]) {
seg[to[j]].push_back({s[i] - s[j], j - i, to[j] - i});
}
}
vector<vector<vector<int>>> qs(n, vector<vector<int>>(2));
for (int i = 0; i < q; i++) {
if (l[i] > 0) {
qs[l[i] - 1][0].push_back(i);
}
qs[r[i]][1].push_back(i);
}
vector<vector<long long>> fenw(4, vector<long long>(n));
auto Modify = [&](int t, int x, long long v) {
assert(0 <= x);
while (x < n) {
fenw[t][x] += v;
x |= (x + 1);
}
};
auto Query = [&](int t, int x) {
assert(x < n);
long long v = 0;
while (x >= 0) {
v += fenw[t][x];
x = (x & (x + 1)) - 1;
}
return v;
};
auto QueryRange = [&](int t, int l, int r) {
return Query(t, r) - Query(t, l - 1);
};
auto AddInc = [&](int L, int R, int v) {
Modify(0, L, +v);
Modify(1, L, (L - 1) * 1LL * v);
Modify(0, R, -v);
Modify(1, R, -R * 1LL * v);
};
auto Ins = [&](int i, int j) {
AddInc(j - i, n - 1, s[i] - s[j]);
Modify(2, i, s[i] - s[j]);
Modify(3, i, i * 1LL * (s[i] - s[j]));
};
auto Rem = [&](int i, int j) {
AddInc(j - i, n - 1, s[j] - s[i]);
Modify(2, i, s[j] - s[i]);
Modify(3, i, i * 1LL * (s[j] - s[i]));
};
auto Solve = [&](int i, int k) {
long long ret = 0;
ret += Query(0, k) * k;
ret -= Query(1, k);
int low = 0, high = (int) stk.size() - 1, pos = -1;
while (low <= high) {
int mid = low + high >> 1;
if (i - stk[mid] < k) {
pos = mid;
high = mid - 1;
} else {
low = mid + 1;
}
}
if (pos != -1) {
ret -= (k - i) * QueryRange(2, stk[pos], i);
ret -= QueryRange(3, stk[pos], i);
}
return ret;
};
stk.clear();
for (int i = 0; i < n; i++) {
while (!stk.empty() && s[stk.back()] <= s[i]) {
if (stk.size() > 1) {
Rem(stk[stk.size() - 2], stk.back());
}
stk.pop_back();
}
if (!stk.empty()) {
Ins(stk.back(), i);
}
stk.push_back(i);
for (int j : qs[i][0]) {
res[j] -= Solve(i, t[j]);
}
for (int j : qs[i][1]) {
res[j] += Solve(i, t[j]);
}
for (auto& p : seg[i]) {
AddInc(p[1], p[2], p[0]);
}
}
for (int i = 0; i < q; i++) {
cout << res[i] << '\n';
}
return 0;
}
Compilation message
ho_t5.cpp: In lambda function:
ho_t5.cpp:112:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
112 | int mid = low + high >> 1;
| ~~~~^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
254 ms |
56304 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
