#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define pb push_back
#define lb lower_bound
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
typedef long long ll;
using namespace std;
const int mxN=500005;
const int mxM=2200005;
const int mxK=61;
const int MOD=1e9+7;
const ll INF=1e18;
struct segtree{
pii seg[4*mxN];
pii mrg(pii a, pii b){
return pii(min(a.fi, b.fi), max(a.se, b.se));
}
void init(int idx, int s, int e, vector <int> &v){
if(s==e){
seg[idx]=pii(v[s], v[s]);
return;
}
int mid=(s+e)/2;
init(2*idx, s, mid, v);
init(2*idx+1, mid+1, e, v);
seg[idx]=mrg(seg[2*idx], seg[2*idx+1]);
}
pii solv(int idx, int s1, int e1, int s2, int e2){
if(s2>e1 || s1>e2) return pii(MOD, -MOD);
if(s2<=s1 && e1<=e2) return seg[idx];
int mid=(s1+e1)/2;
return mrg(solv(2*idx, s1, mid, s2, e2), solv(2*idx+1, mid+1, e1, s2, e2));
}
};
struct node{
int val;
int l, r;
node() : val(), l(), r() {}
node(int val, int l, int r) : val(val), l(l), r(r) {}
};
struct pst{
vector <node> tree;
int root[100010]={};
int sz=1, L, R;
void init_s(int a, int b){
tree.resize(2300000);
root[0]=sz++;
L=a, R=b;
init_t(root[0], L, R);
}
void init_t(int idx, int s, int e){
if(s==e) return;
int mid=(s+e)/2;
tree[idx].l=sz++;
init_t(sz-1, s, mid);
tree[idx].r=sz++;
init_t(sz-1, mid+1, e);
}
void upd_s(int now, int pos){
root[now]=sz++;
upd_t(root[now], root[now-1], L, R, pos);
}
void upd_t(int idx1, int idx2, int s, int e, int pos){
tree[idx1].val=tree[idx2].val;
tree[idx1].val++;
if(s==e) return;
int mid=(s+e)/2;
if(pos<=mid) tree[idx1].l=sz++;
else tree[idx1].r=sz++;
if(pos<=mid) upd_t(sz-1, tree[idx2].l, s, mid, pos), tree[idx1].r=tree[idx2].r;
else upd_t(sz-1, tree[idx2].r, mid+1, e, pos), tree[idx1].l=tree[idx2].l;
}
int solv_s(int rt, int s, int e){
return solv_t(root[rt], L, R, s, e);
}
int solv_t(int idx, int s1, int e1, int s2, int e2){
if(s2>e1 || s1>e2) return 0;
if(s2<=s1 && e1<=e2) return tree[idx].val;
int mid=(s1+e1)/2;
return solv_t(tree[idx].l, s1, mid, s2, e2)+solv_t(tree[idx].r, mid+1, e1, s2, e2);
}
int bin_searchl_t(int idx, int s1, int e1, int s2, int e2){
if(s2>e1 || s1>e2) return 0;
if(s1==e1){
return (tree[idx].val==1 ? s1 : 0);
}
if(s2<=s1 && e1<=e2){
if(tree[idx].val!=0){
int mid=(s1+e1)/2;
int lres=bin_searchl_t(tree[idx].l, s1, mid, s2, e2);
if(lres!=0) return lres;
return bin_searchl_t(tree[idx].r, mid+1, e1, s2, e2);
}
else return 0;
}
int mid=(s1+e1)/2;
int lres=bin_searchl_t(tree[idx].l, s1, mid, s2, e2);
if(lres!=0) return lres;
return bin_searchl_t(tree[idx].r, mid+1, e1, s2, e2);
}
int bin_searchr_t(int idx, int s1, int e1, int s2, int e2){
if(s2>e1 || s1>e2) return 0;
if(s1==e1){
return (tree[idx].val==1 ? s1 : 0);
}
if(s2<=s1 && e1<=e2){
if(tree[idx].val!=0){
int mid=(s1+e1)/2;
int rres=bin_searchr_t(tree[idx].r, mid+1, e1, s2, e2);
if(rres!=0) return rres;
return bin_searchr_t(tree[idx].l, s1, mid, s2, e2);
}
else return 0;
}
int mid=(s1+e1)/2;
int rres=bin_searchr_t(tree[idx].r, mid+1, e1, s2, e2);
if(rres!=0) return rres;
return bin_searchr_t(tree[idx].l, s1, mid, s2, e2);
}
int bin_searchl_s(int rt, int s, int e){
return bin_searchl_t(root[rt], L, R, s, e);
}
int bin_searchr_s(int rt, int s, int e){
return bin_searchr_t(root[rt], L, R, s, e);
}
};
int N, Q;
int A[mxN];
int qry[mxN][3];
int F[mxN];
vector <pii> Dp, Dm;
void input(){
cin >> N >> Q;
A[0]=-1e9-10, A[1]=1e9+10;
for(int i=2;i<=N+1;i++) cin >> A[i];
A[N+2]=1e9+10, A[N+3]=-1e9-10;
for(int i=1;i<=Q;i++){
int l, r, d;
cin >> l >> r >> d;
qry[i][0]=l;
qry[i][1]=r;
qry[i][2]=d;
}
}
segtree T1;
void make_F(){
vector <int> v(N+4);
for(int i=0;i<=N+3;i++) v[i]=A[i];
T1.init(1, 0, N+3, v);
stack <int> stk;
stk.push(1);
for(int i=2;i<=N+1;i++){
while(A[stk.top()]<A[i]) stk.pop();
if(A[i]<A[i-1] || A[i]<A[i+1]) continue;
int mini=(stk.top()==i-1 ? MOD : T1.solv(1, 0, N+3, stk.top()+1, i-1).fi);
F[i]=A[i]-mini;
stk.push(i);
}
while(stk.size()) stk.pop();
stk.push(N+2);
for(int i=N+1;i>=2;i--){
while(A[stk.top()]<A[i]) stk.pop();
if(A[i]<A[i-1] || A[i]<A[i+1]) continue;
int mini=(stk.top()==i+1 ? MOD : T1.solv(1, 0, N+3, i+1, stk.top()-1).fi);
F[i]=min(F[i], A[i]-mini);
stk.push(i);
}
while(stk.size()) stk.pop();
stk.push(0);
for(int i=2;i<=N+1;i++){
while(A[stk.top()]>A[i]) stk.pop();
if(A[i]>A[i-1] || A[i]>A[i+1]) continue;
int maxi=(stk.top()==i-1 ? -MOD : T1.solv(1, 0, N+3, stk.top()+1, i-1).se);
F[i]=maxi-A[i];
stk.push(i);
}
stk.push(N+3);
for(int i=N+1;i>=2;i--){
while(A[stk.top()]>A[i]) stk.pop();
if(A[i]>A[i-1] || A[i]>A[i+1]) continue;
int maxi=(stk.top()==i+1 ? -MOD : T1.solv(1, 0, N+3, i+1, stk.top()-1).se);
F[i]=min(F[i], maxi-A[i]);
F[i]*=-1;
stk.push(i);
}
//for(int i=1;i<=N;i++) printf("F[%d]=%d\n", i, F[i+1]);
for(int i=2;i<=N+1;i++) if(F[i]>0) Dp.emplace_back(F[i], i);
for(int i=2;i<=N+1;i++) if(F[i]<0) Dm.emplace_back(-F[i], i);
sort(all(Dp), [](pii a, pii b){return a>b;});
sort(all(Dm), [](pii a, pii b){return a>b;});
/*
for(auto [x, y] : Dp) printf("(%d %d) ", x, y);
printf("\n");
for(auto [x, y] : Dm) printf("(%d %d) ", x, y);
printf("\n");
*/
}
pst T2, T3;
void make_tree(){
T2.init_s(2, N+1);
for(int i=0;i<Dp.size();i++){
T2.upd_s(i+1, Dp[i].se);
}
T3.init_s(2, N+1);
for(int i=0;i<Dm.size();i++){
T3.upd_s(i+1, Dm[i].se);
}
}
void init(int n, vector <int> v){
N=n;
A[0]=-1e9-10, A[1]=1e9+10;
for(int i=2;i<=N+1;i++) A[i]=v[i-2];
A[N+2]=1e9+10, A[N+3]=-1e9-10;
make_F();
make_tree();
}
int max_towers(int l, int r, int d){
l+=2, r+=2;
int lp=N+3, lm=N+3, rp=0, rm=0, mcnt=0, pcnt=0;
int mxidx, mnidx;
mxidx=lower_bound(all(Dp), pii(d, 0), [](pii a, pii b){return a>b;})-Dp.begin();
mnidx=lower_bound(all(Dm), pii(d, 0), [](pii a, pii b){return a>b;})-Dm.begin();
pcnt=T2.solv_s(mxidx, l, r);
mcnt=T3.solv_s(mnidx, l, r);
if(pcnt!=0){
rp=T2.bin_searchr_s(mxidx, l, r);
lp=T2.bin_searchl_s(mxidx, l, r);
/*
int s=l, e=r+1;
while(s!=e){
int mid=(s+e)/2;
if(T2.solv_s(mxidx, mid, r)==0) e=mid;
else s=mid+1;
}
rp=s-1;
s=l, e=r;
while(s!=e){
int mid=(s+e)/2;
if(T2.solv_s(mxidx, l, mid)==0) s=mid+1;
else e=mid;
}
lp=s;
*/
}
if(mcnt!=0){
rm=T3.bin_searchr_s(mnidx, l, r);
lm=T3.bin_searchl_s(mnidx, l, r);
/*
int s=l, e=r+1;
while(s!=e){
int mid=(s+e)/2;
if(T3.solv_s(mnidx, mid, r)==0) e=mid;
else s=mid+1;
}
rm=s-1;
s=l, e=r;
while(s!=e){
int mid=(s+e)/2;
if(T3.solv_s(mnidx, l, mid)==0) s=mid+1;
else e=mid;
}
lm=s;
*/
}
/*
for(int i=l;i<=r;i++){
if(F[i]>=d) pcnt++, rp=max(rp, i), lp=min(lp, i);
if(F[i]<=-d) mcnt++, rm=max(rm, i), lm=min(lm, i);
}
*/
if(rp!=0 && rp>=rm){
bool ok=false;
if(rp!=r && T1.solv(1, 0, N+3, rp+1, r).fi<=A[rp]-d) ok=true;
if(ok) mcnt++;
}
if(lp!=N+3 && lp<=lm){
bool ok=false;
if(lp!=l && T1.solv(1, 0, N+3, l, lp-1).fi<=A[lp]-d) ok=true;
if(ok) mcnt++;
}
return (mcnt<=1 ? 1 : mcnt);
}
int main()
{
gibon
input();
make_F();
make_tree();
for(int i=1;i<=Q;i++){
printf("%d\n", max_towers(qry[i][0], qry[i][1], qry[i][2]));
}
}
Compilation message
towers.cpp: In function 'void make_tree()':
towers.cpp:211:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
211 | for(int i=0;i<Dp.size();i++){
| ~^~~~~~~~~~
towers.cpp:215:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
215 | for(int i=0;i<Dm.size();i++){
| ~^~~~~~~~~~
/usr/bin/ld: /tmp/ccQa6QC2.o: in function `main':
stub.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccVcrDj4.o:towers.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
