// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #include <x86intrin.h>
#include <bits/stdc++.h>
#include <chrono>
#include <random>
// @author: Vlapos
namespace operators
{
template <typename T1, typename T2>
std::istream &operator>>(std::istream &in, std::pair<T1, T2> &x)
{
in >> x.first >> x.second;
return in;
}
template <typename T1, typename T2>
std::ostream &operator<<(std::ostream &out, std::pair<T1, T2> x)
{
out << x.first << " " << x.second;
return out;
}
template <typename T1>
std::istream &operator>>(std::istream &in, std::vector<T1> &x)
{
for (auto &i : x)
in >> i;
return in;
}
template <typename T1>
std::ostream &operator<<(std::ostream &out, std::vector<T1> &x)
{
for (auto &i : x)
out << i << " ";
return out;
}
template <typename T1>
std::ostream &operator<<(std::ostream &out, std::set<T1> &x)
{
for (auto &i : x)
out << i << " ";
return out;
}
}
// name spaces
using namespace std;
using namespace operators;
// end of name spaces
// defines
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define pll pair<ll, ll>
#define f first
#define s second
#define uint unsigned int
#define all(vc) vc.begin(), vc.end()
// end of defines
// usefull stuff
void boost()
{
ios_base ::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
}
inline int getbit(int &x, int &bt) { return (x >> bt) & 1; }
const int dx4[4] = {-1, 0, 0, 1};
const int dy4[4] = {0, -1, 1, 0};
const int dx8[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
const int dy8[8] = {-1, -0, 1, -1, 1, -1, 0, 1};
const ll INF = (1e15) + 500;
const int BIG = (2e9) + 500;
const int MOD7 = (1e9) + 7;
const int MOD9 = (1e9) + 9;
const uint MODFFT = 998244353;
// #define int ll
struct segTreeAdd
{
vector<pll> tree;
int sz;
void init(int n)
{
sz = 1;
while (sz < n)
sz *= 2;
tree.resize(2 * sz, {0, 0});
}
void upd(int v, int lv, int rv, int val)
{
tree[v].s += val;
tree[v].f += (rv - lv) * (ll)val;
}
void push(int v, int lv, int rv)
{
if (rv - lv == 1 or tree[v].s == 0)
return;
int m = (lv + rv) >> 1;
upd(v * 2 + 1, lv, m, tree[v].s);
upd(v * 2 + 2, m, rv, tree[v].s);
tree[v].s = 0;
}
void update(int l, int r, int val, int v, int lv, int rv)
{
push(v, lv, rv);
if (l <= lv and rv <= r)
{
upd(v, lv, rv, val);
return;
}
if (rv <= l or r <= lv)
return;
int m = (lv + rv) >> 1;
update(l, r, val, v * 2 + 1, lv, m);
update(l, r, val, v * 2 + 2, m, rv);
tree[v].f = tree[v * 2 + 1].f + tree[v * 2 + 2].f;
}
void update(int l, int r, int val)
{
update(l, r, val, 0, 0, sz);
}
ll get(int l, int r, int v, int lv, int rv)
{
push(v, lv, rv);
if (l <= lv and rv <= r)
return tree[v].f;
if (rv <= l or r <= lv)
return 0;
int m = (lv + rv) >> 1;
return get(l, r, v * 2 + 1, lv, m) + get(l, r, v * 2 + 2, m, rv);
}
ll get(int l, int r)
{
return get(l, r, 0, 0, sz);
}
};
struct test
{
struct op
{
int t, l, r, val;
};
vector<vector<op>> reqs;
int n, q;
void addTriangle(int l, int r, int val)
{
if (l == r)
return;
reqs[0].push_back({0, 0, n - l + 1, +val});
reqs[0].push_back({1, r, n, -val});
reqs[r - l].push_back({1, r, n, +val});
reqs[r - l].push_back({0, 0, n - l + 1, -val});
}
void solve(int testcase)
{
boost();
cin >> n >> q;
vector<int> a(n), L(n);
cin >> a;
reqs.resize(3 * n);
{
stack<int> bf;
for (int i = 0; i < n; ++i)
{
while (bf.size() and a[bf.top()] <= a[i])
bf.pop();
if (bf.size())
L[i] = bf.top();
else
L[i] = i - n;
bf.push(i);
}
}
{
stack<int> bf;
for (int i = n - 1; i >= 0; --i)
{
while (bf.size() and a[bf.top()] < a[i])
bf.pop();
int curL = L[i] + 1;
int curR = bf.size() ? bf.top() : n;
addTriangle(curL, curR, a[i]); // [L, R)
addTriangle(curL, i, -a[i]); // [L, R)
addTriangle(i + 1, curR, -a[i]);
bf.push(i);
}
}
vector<vector<pair<int, pii>>> qrs(n + 10);
vector<ll> ans(q);
for (int i = 0; i < n; ++i)
{
int t, l, r;
cin >> t >> l >> r;
--l;
qrs[t].pb({i, {l, r}});
}
segTreeAdd diag, square;
diag.init(n * 3);
square.init(n + 1);
for (int t = 0; t <= n; ++t)
{
for (op req : reqs[t])
{
if (req.t == 0)
// triangle
diag.update(req.l, req.r, req.val);
else
// square
square.update(req.l, req.r, req.val);
}
// for (int i = 0; i < n; ++i)
// {
// cout << diag.get(n - i + t, n - i + t + 1) + square.get(i, i + 1) << ' ';
// }
// cout << "\n";
for (auto &[id, seg] : qrs[t])
{
auto [l, r] = seg;
ans[id] = diag.get(n - (r - 1) + t, n - l + t + 1) + square.get(l, r);
}
}
cout << ans << "\n";
}
};
main()
{
boost();
int q = 1;
// cin >> q;
for (int i = 0; i < q; i++)
{
test t;
t.solve(i);
}
return 0;
}
//[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]//
// //
// Coded by Der_Vlἀpos //
// //
//[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]//
Compilation message
ho_t5.cpp:269:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
269 | main()
| ^~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
677 ms |
98160 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
