#include <bits/stdc++.h>
#include "towers.h"
using namespace std;
const int INF = 2e9;
#define FOR(i,a,b) for(int i=(a); i<(b); ++i)
#define ROF(i,a,b) for(int i=(b)-1; i>=(a); --i)
typedef vector<int> vi;
typedef pair<int,int> ii;
struct SegmentTree {
int v;
int N;
int minH,maxH;
SegmentTree* left;
SegmentTree* right;
SegmentTree(SegmentTree* st) {
v = st->v;
N = st->N;
minH = st->minH;
maxH = st->maxH;
left = st->left;
right = st->right;
}
SegmentTree(int l, int r, vi &init, vi &H) {
if(r-l==1) {
left = right = nullptr;
v = init[l];
minH = maxH = H[l];
N = H.size();
} else {
int m = (l+r)/2;
left = new SegmentTree(l,m,init,H);
right = new SegmentTree(m,r,init,H);
pull();
}
}
SegmentTree* modify(int p, int l, int r, int val) {
if(l == r) return nullptr;
SegmentTree* st = new SegmentTree(this);
if(r-l == 1) {
st->v += val;
} else {
int m = (l+r)/2;
if(p < m) st->left = left->modify(p,l,m,val);
else st->right = right->modify(p,m,r,val);
st->pull();
}
return st;
}
SegmentTree* modify(int p, int val) {
return modify(p,0,N,val);
}
int rangeQuerySum(int l, int r, int _l, int _r) {
if(l >= _r || _l >= r) {
return 0;
} else if(_l <= l && r <= _r) {
return v;
} else {
int m = (l+r)/2;
int lq = left->rangeQuerySum(l,m,_l,_r);
int rq = right->rangeQuerySum(m,r,_l,_r);
return lq+rq;
}
}
int rangeQuerySum(int l, int r) {
return rangeQuerySum(0,N,l,r);
}
int rangeQueryMinHeight(int l, int r, int _l, int _r) {
if(l >= _r || _l >= r) {
return INF;
} else if(_l <= l && r <= _r) {
return minH;
} else {
int m = (l+r)/2;
int lq = left->rangeQueryMinHeight(l,m,_l,_r);
int rq = right->rangeQueryMinHeight(m,r,_l,_r);
return min(lq,rq);
}
}
int rangeQueryMinHeight(int l, int r) {
return rangeQueryMinHeight(0,N,l,r);
}
int findFirst(int l, int r, int _l, int _r) {
if(v==0 || l >= _r || _l >= r) {
return -1;
} else if(r-l==1) {
return l;
} else {
int m = (l+r)/2;
int ans = left->findFirst(l,m,_l,_r);
if(ans == -1) return right->findFirst(m,r,_l,_r);
else return ans;
}
}
int findFirst(int l, int r) {
return findFirst(0,N,l,r);
}
int findLast(int l, int r, int _l, int _r) {
if(v==0 || l >= _r || _l >= r) {
return -1;
} else if(r-l==1) {
return l;
} else {
int m = (l+r)/2;
int ans = right->findLast(m,r,_l,_r);
if(ans == -1) return left->findLast(l,m,_l,_r);
else return ans;
}
}
int findLast(int l, int r) {
return findLast(0,N,l,r);
}
void pull() {
N = left->N;
v = left->v + right->v;
minH = min(left->minH,right->minH);
maxH = max(left->maxH,right->maxH);
}
};
map<int,SegmentTree*> mp;
vector<int> heights;
void init(int N, std::vector<int> H) {
heights = H;
vi init(N,0);
FOR(i,0,N) {
if(i == 0 || i == N-1 || H[i] > max(H[i-1],H[i+1]) || H[i] < min(H[i-1],H[i+1])) {
init[i] = 1;
}
}
priority_queue<pair<int,ii>,vector<pair<int,ii>>,greater<pair<int,ii>>> pq;
int prvH = -1, prvArg = -1;
FOR(i,0,N) {
if(init[i] == 1) {
if(prvH != -1) {
pq.push({abs(prvH-H[i]),{prvArg,i}});
}
prvH = H[i];
prvArg = i;
}
}
SegmentTree* st = new SegmentTree(0,N,init,H);
mp[1] = st;
while(!pq.empty()) {
auto [d,v] = pq.top(); pq.pop();
auto [i,j] = v;
if(st->findFirst(i,i+1) == i && st->findFirst(j,j+1) == j) {
int prv = st->findLast(0,i);
int nxt = st->findFirst(j+1,N);
if(prv != -1 && nxt != -1) {
st = st->modify(i,-1);
st = st->modify(j,-1);
pq.push({abs(H[prv]-H[nxt]),{prv,nxt}});
} else if(nxt != -1) {
st = st->modify(i,-1);
} else {
st = st->modify(j,-1));
}
mp[d+1] = st;
}
}
assert(st->findFirst(0,N) == st->findLast(0,N));
return;
}
int max_towers(int L, int R, int D) {
SegmentTree* st = prev(mp.upper_bound(D))->second;
int ans = st->rangeQuerySum(L,R+1);
if(ans == 0) return 1;
else if(ans == 1) {
int tow = st->findFirst(L,R+1);
assert(tow == st->findLast(L,R+1));
int prefMin = st->rangeQueryMinHeight(L,tow);
if(prefMin <= heights[tow] - D) ans++;
int suffMin = st->rangeQueryMinHeight(tow+1,R+1);
if(suffMin <= heights[tow] - D) ans++;
return (ans+1)/2;
} else {
int fi1 = st->findFirst(L,R+1);
int fi2 = st->findFirst(fi1+1,R+1);
int la1 = st->findLast(L,R+1);
int la2 = st->findLast(L,la1);
if(heights[fi1] > heights[fi2]) {
int prefMin = st->rangeQueryMinHeight(L,fi1);
if(prefMin <= heights[fi1] - D) ans++;
else ans--;
}
if(heights[la1] > heights[la2]) {
int suffMin = st->rangeQueryMinHeight(la1+1,R+1);
if(suffMin <= heights[la1] - D) ans++;
else ans--;
}
assert(ans%2 == 1);
return (ans+1)/2;
}
return 0;
}
Compilation message
towers.cpp: In function 'void init(int, std::vector<int>)':
towers.cpp:176:26: error: expected ';' before ')' token
176 | st = st->modify(j,-1));
| ^
| ;
