#include <bits/stdc++.h>
using namespace std;
#ifdef MIKU
#define debug(x...) cout << '[' << #x << "] : ", dout(x)
void dout() { cout << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif
#define int long long
#define fs first
#define sc second
#define mp make_pair
typedef pair<int, int> pii;
typedef pair<pii, pii> p4i;
const int MXN = 400005;
int n, q, a[MXN], l[MXN], r[MXN], ans[MXN];
int ql[MXN], qr[MXN], qt[MXN];
vector<p4i> op;
struct BIT {
int n, val[MXN];
void init(int _n) {
n = _n;
fill(val + 1, val + n + 1, 0);
}
void modify(int id, int v) {
for (; id <= n; id += (id & -id)) val[id] += v;
}
int query(int id) {
int ans = 0;
for (; id > 0; id -= (id & -id)) ans += val[id];
return ans;
}
};
struct BBIT {
BIT A, B;
void init(int _n) {
A.init(_n);
B.init(_n);
}
void modify(int id, int v) {
A.modify(id, v);
B.modify(id, id * v);
}
int query(int id) {
return (id + 1) * A.query(id) - B.query(id);
}
int query(int l, int r) {
return query(r) - query(l - 1);
}
};
struct HBBIT {
int sr;
BBIT B;
void init(int _n, int _sr) {
B.init(_n);
sr = _sr;
}
void move() {
sr--;
}
void modify(int id, int v) {
B.modify(sr + id, v);
}
int query(int id) {
return B.query(sr + id);
}
};
struct DS {
BBIT S;
HBBIT T;
void init() {
S.init(MXN);
T.init(MXN, MXN / 2);
}
void move() {
T.move();
}
void modify(int id, int v) {
S.modify(id, v);
T.modify(id + 1, -v);
}
int query(int id) {
return S.query(id) + T.query(id);
}
int query(int l, int r) {
return query(r) - query(l - 1);
}
} B;
void FIND_L() {
stack<pii> st;
st.push(mp(LLONG_MAX, -1LL));
for (int i = 1; i <= n; i++) {
while (st.top().fs < a[i]) st.pop();
l[i] = st.top().sc;
st.push(mp(a[i], i));
}
}
void FIND_R() {
stack<pii> st;
st.push(mp(LLONG_MAX, -1LL));
for (int i = n; i > 0; i--) {
while (st.top().fs <= a[i]) st.pop();
r[i] = st.top().sc;
st.push(mp(a[i], i));
}
}
void BOX(int id) {
op.push_back(mp(mp(0LL, 2LL), mp(id, a[id])));
if (l[id] != -1) op.push_back(mp(mp(id - l[id], 2LL), mp(id, -a[id])));
if (r[id] != -1) op.push_back(mp(mp(r[id] - id, 2LL), mp(r[id], -a[id])));
if (l[id] != -1 && r[id] != -1) op.push_back(mp(mp(r[id] - l[id], 2LL), mp(r[id], a[id])));
}
void BOX() {
for (int i = 1; i <= n; i++) op.push_back(mp(mp(i, 1LL), mp(0LL, 0LL)));
for (int i = 1; i <= n; i++) op.push_back(mp(mp(qt[i], 3LL), mp(i, 0LL)));
for (int i = 1; i <= n; i++) BOX(i);
for (int i = 1; i <= n; i++) debug(i, l[i], r[i]);
}
void miku() {
cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> a[i];
FIND_L();
FIND_R();
for (int i = 1; i <= q; i++) cin >> qt[i] >> ql[i] >> qr[i];
BOX();
debug("PRING");
sort(op.begin(), op.end());
B.init();
for (auto &i : op) {
if (i.fs.sc == 1) {
// for (int i = 1; i <= n; i++) cout << B.query(i, i) << ' ';
// cout << endl;
debug("MOVE");
B.move();
} else if (i.fs.sc == 2) {
debug("MODIFY", i.sc.fs, i.sc.sc);
B.modify(i.sc.fs, i.sc.sc);
} else if (i.fs.sc == 3) {
debug("QUERY");
ans[i.sc.fs] = B.query(ql[i.sc.fs], qr[i.sc.fs]);
}
}
for (int i = 1; i <= q; i++) cout << ans[i] << '\n';
}
int32_t main() {
cin.tie(0) -> sync_with_stdio(false);
miku();
return 0;
}
Compilation message
ho_t5.cpp: In function 'void BOX()':
ho_t5.cpp:10:20: warning: statement has no effect [-Wunused-value]
10 | #define debug(...) 39
| ^~
ho_t5.cpp:130:34: note: in expansion of macro 'debug'
130 | for (int i = 1; i <= n; i++) debug(i, l[i], r[i]);
| ^~~~~
ho_t5.cpp: In function 'void miku()':
ho_t5.cpp:10:20: warning: statement has no effect [-Wunused-value]
10 | #define debug(...) 39
| ^~
ho_t5.cpp:140:5: note: in expansion of macro 'debug'
140 | debug("PRING");
| ^~~~~
ho_t5.cpp:10:20: warning: statement has no effect [-Wunused-value]
10 | #define debug(...) 39
| ^~
ho_t5.cpp:147:13: note: in expansion of macro 'debug'
147 | debug("MOVE");
| ^~~~~
ho_t5.cpp:10:20: warning: statement has no effect [-Wunused-value]
10 | #define debug(...) 39
| ^~
ho_t5.cpp:150:13: note: in expansion of macro 'debug'
150 | debug("MODIFY", i.sc.fs, i.sc.sc);
| ^~~~~
ho_t5.cpp:10:20: warning: statement has no effect [-Wunused-value]
10 | #define debug(...) 39
| ^~
ho_t5.cpp:153:13: note: in expansion of macro 'debug'
153 | debug("QUERY");
| ^~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
7 ms |
27228 KB |
Output is correct |
| 2 |
Correct |
4 ms |
27228 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
27228 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
7 ms |
27228 KB |
Output is correct |
| 2 |
Correct |
283 ms |
84140 KB |
Output is correct |
| 3 |
Incorrect |
247 ms |
83376 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
7 ms |
27228 KB |
Output is correct |
| 2 |
Incorrect |
277 ms |
84020 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
223 ms |
65988 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
7 ms |
27228 KB |
Output is correct |
| 2 |
Correct |
4 ms |
27228 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
27228 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
