#include "towers.h"
#include <bits/stdc++.h>
using std::vector;
using std::string;
using std::cin;
using std::cout;
using ll = int;
using vi = vector<ll>;
using vii = vector<vi>;
using pii = std::pair<ll,ll>;
#define ln "\n"
#define rep(i,j,k) for(ll i=ll(j); i<ll(k); i++)
#define REP(i,j,k) for(ll i=ll(j); i<=ll(k); i++)
#define per(i,j,k) for(ll i=ll(j); i>=ll(k); i--)
#define all(a) a.begin(), a.end()
#define mp std::make_pair
#define pb emplace_back
constexpr ll inf = (1<<30)+(1<<29)+(1<<28);
ll N;
vi H;
ll D;
vi right, left;
constexpr ll di = 30;
ll sz;
vii pr, mr, pl, ml;
vii sum;
void init(int n, std::vector<int> h) {
N = n;
H.resize(N);
right.resize(N);
left.resize(N);
rep(i,0,N) H[i] = h[i];
D = -1;
}
int max_towers(int L, int R, int d) {
if(D == -1){
D = d;
{
sz = N/di+100;
sum.resize(sz, vi(sz));
pr.resize(N+2);
mr.resize(N+2);
pl.resize(N+2);
ml.resize(N+2);
std::deque<ll> ima, vma, imi, vmi;
ima.pb(-3);
vma.pb(-inf);
imi.pb(-2);
vmi.pb(inf);
rep(i,0,N){
ll large = lower_bound(all(vmi), H[i]+D)-vmi.begin();
large = imi[large];
ll small = lower_bound(all(vma),H[i])-vma.begin()-1;
small = ima[small];
if(small >= large) left[i] = small+1;
else left[i] = -1;
while(true){
if(vma[vma.size()-1] > H[i]) vma.pop_back(), ima.pop_back();
else break;
}
vma.pb(H[i]);
ima.pb(i);
while(true){
if(vmi[0] < H[i]) vmi.pop_front(), imi.pop_front();
else break;
}
vmi.emplace_front(H[i]);
imi.emplace_front(i);
}
}
{
std::deque<ll> ima, vma, imi, vmi;
ima.pb(N+3);
vma.pb(-inf);
imi.pb(N+2);
vmi.pb(inf);
per(i,N-1,0){
ll large = lower_bound(all(vmi), H[i]+D)-vmi.begin();
large = imi[large];
ll small = lower_bound(all(vma),H[i])-vma.begin()-1;
small = ima[small];
if(small <= large) right[i] = small-1;
else right[i] = N;
while(true){
if(vma[vma.size()-1] > H[i]) vma.pop_back(), ima.pop_back();
else break;
}
vma.pb(H[i]);
ima.pb(i);
while(true){
if(vmi[0] < H[i]) vmi.pop_front(), imi.pop_front();
else break;
}
vmi.emplace_front(H[i]);
imi.emplace_front(i);
}
}
rep(i,0,N){
left[i]++;
right[i]++;
ll ld = (left[i]+di-1)/di;
ll rd = right[i]/di;
sum[ld][rd]++;
ll id = i/di;
sum[ld][id]--;
id = (i+2+di-1)/di;
sum[id][rd]--;
pr[right[i]].pb(left[i]);
pl[left[i]].pb(right[i]);
ml[i+2].pb(right[i]);
ml[left[i]].pb(i);
mr[i].pb(left[i]);
mr[right[i]].pb(i+2);
}
per(l,sz,1){
rep(i,0,sz){
ll j = i+l;
if(j >= sz) break;
if(i) sum[i][j] += sum[i-1][j];
if(j+1 < sz) sum[i][j] += sum[i][j+1];
if(i && j+1<sz) sum[i][j] -= sum[i-1][j+1];
}
}
rep(i,0,pr.size()){
sort(all(pr[i]));
sort(all(pl[i]));
sort(all(mr[i]));
sort(all(ml[i]));
}
}
ll ans = 0;
if(R-L <= 1000){
REP(i,L,R){
if(left[i]-1 <= L && R <= right[i]-1) ans++;
}
return ans;
}
L++, R++;
ll ld = L/di;
ll rd = (R+di-1)/di;
ans = sum[ld][rd];
REP(i, ld*di+1, L){
ans += pl[i].end()-lower_bound(all(pl[i]), rd*di);
ans -= ml[i].end()-lower_bound(all(ml[i]), rd*di);
}
rep(i,R,rd*di){
if(i >= int(pr.size())) continue;
ans += upper_bound(all(pr[i]), L)-pr[i].begin();
ans -= upper_bound(all(mr[i]), L)-mr[i].begin();
}
return ans;
}
int main(){
ll n,Q; cin >> n >> Q;
vi h(n);
rep(i,0,n) cin >> h[i];
init(n,h);
while(Q--){
ll L,R,d; cin >> L >> R >> d;
cout << max_towers(L,R,d) << ln;
}
}
Compilation message
/usr/bin/ld: /tmp/ccCFNmlp.o: in function `main':
stub.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccrvOB0p.o:towers.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
