#include <bits/stdc++.h>
using namespace std;
const long long INF1 = 1000000000000;
const long long INF2 = 100000000000000;
struct lazy_segment_tree{
int N;
vector<long long> ST, lazy;
lazy_segment_tree(vector<long long> &A){
int N2 = A.size();
N = 1;
while (N < N2){
N *= 2;
}
ST = vector<long long>(N * 2 - 1, -INF2);
for (int i = 0; i < N2; i++){
ST[N - 1 + i] = A[i];
}
for (int i = N - 2; i >= 0; i--){
ST[i] = max(ST[i * 2 + 1], ST[i * 2 + 2]);
}
lazy = vector<long long>(N * 2 - 1, 0);
}
void eval(int i){
if (laz[i] != 0){
if (i < N - 1){
lazy[i * 2 + 1] += lazy[i];
lazy[i * 2 + 2] += lazy[i];
}
ST[i] += lazy[i];
lazy[i] = 0;
}
}
void range_add(int L, int R, long long x, int i, int l, int r){
eval(i);
if (r <= L || R <= l){
} else if (L <= l && r <= R){
lazy[i] += x;
eval(i);
} else {
int m = (l + r) / 2;
range_add(L, R, x, i * 2 + 1, l, m);
range_add(L, R, x, i * 2 + 2, m, r);
ST[i] = max(ST[i * 2 + 1], ST[i * 2 + 2]);
}
}
void range_add(int L, int R, long long x){
range_add(L, R, x, 0, 0, N);
}
long long range_max(int L, int R, int i, int l, int r){
eval(i);
if (r <= L || R <= l){
return -INF2;
} else if (L <= l && r <= R){
return ST[i];
} else {
int m = (l + r) / 2;
return max(range_max(L, R, i * 2 + 1, l, m), range_max(L, R, i * 2 + 2, m, r));
}
}
long long range_max(int L, int R){
return range_max(L, R, 0, 0, N);
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, M;
cin >> N >> M;
vector<long long> w(N);
for (int i = 0; i < N; i++){
cin >> w[i];
}
vector<int> l(M), r(M);
vector<long long> k(M);
for (int i = 0; i < M; i++){
cin >> l[i] >> r[i] >> k[i];
l[i]--;
}
vector<vector<int>> query(N);
for (int i = 0; i < M; i++){
query[l[i]].push_back(i);
}
lazy_segment_tree ST(w);
stack<int> st;
st.push(N);
vector<long long> mx(M, 0);
for (int i = N - 1; i >= 0; i--){
while (st.top() != N){
int p = st.top();
if (w[i] <= w[p]){
break;
}
st.pop();
int q = st.top();
ST.range_add(p, p + 1, INF1);
ST.range_add(p + 1, q, -w[p]);
}
int p = st.top();
ST.range_add(i, i + 1, -INF1);
ST.range_add(i + 1, p, w[i]);
st.push(i);
for (int j : query[i]){
mx[j] = ST.range_max(i, r[j]);
}
}
for (int i = 0; i < M; i++){
if (mx[i] <= k[i]){
cout << 1 << "\n";
} else {
cout << 0 << "\n";
}
}
}
Compilation message
sortbooks.cpp: In member function 'void lazy_segment_tree::eval(int)':
sortbooks.cpp:24:9: error: 'laz' was not declared in this scope; did you mean 'lazy'?
24 | if (laz[i] != 0){
| ^~~
| lazy
