#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define RE(a,b) REP(a,0,b)
#define FOR(a,b) for(auto& a:b)
#define pb push_back
#define fi first
#define se second
#define all(a) a.begin(), a.end()
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
const int INF=1e9;
const int MX=4e5+100;
int n, k;
vi r;
int h[MX];
int htoi[MX];
int nxtUp[MX][20];
int nxtDo[MX][20];
int END;
struct Seg {
ii SEG[MX*4]; int LAZY[MX*4];
void build(const vi& f, int p=0, int l=0, int r=n-1) {
LAZY[p] = 0;
if(l == r) {
SEG[p] = {f[l], l};
return;
}
int m=(l+r)/2;
build(f,p*2+1,l,m);
build(f,p*2+2,m+1,r);
SEG[p] = max(SEG[p*2+1], SEG[p*2+2]);
}
void add(int i, int j, int v, int lazy=0, int p=0, int l=0, int r=n-1) {
LAZY[p] += lazy;
SEG[p].fi += lazy;
if(j < l || i > r) return;
if(i <= l && j >= r) {
SEG[p].fi += v;
LAZY[p] += v;
return;
}
int m=(l+r)/2;
add(i,j,v,LAZY[p],p*2+1,l,m);
add(i,j,v,LAZY[p],p*2+2,m+1,r);
LAZY[p] = 0;
SEG[p] = max(SEG[p*2+1], SEG[p*2+2]);
}
void addRound(int i, int j, int v) {
if(i >= n) i-=n, j-=n;
if(j < n) {
add(i,j,v);
} else {
add(i,n-1,v);
add(0,j-n,v);
}
}
} seg1, seg2;
struct SegMin {
int SEG[MX*2];
void build() {
RE(i,n*2) SEG[i+n*2]=END;
REV(i,1,n*2) SEG[i]=min(SEG[i*2],SEG[i*2+1]);
}
void set(int x, int v) {
for(SEG[x+=n*2]=v; x>1; x/=2) SEG[x/2]=min(SEG[x],SEG[x^1]);
}
int get(int l, int r) {
int ans=INF;
for(l+=n*2,r+=n*2; l<r; l/=2, r/=2) {
if(l&1) ans = min(ans,SEG[l++]);
if(r&1) ans = min(ans,SEG[--r]);
}
return ans;
}
} segH;
void init(int _k, vi _r) {
k = _k; r = _r;
n = r.size();
END = n*2;
seg1.build(r);
seg2.build(vi(n,0));
RE(i,n) {
while(seg1.SEG[0].fi == k-1) {
int x = seg1.SEG[0].se;
seg1.add(x,x,-INF);
seg2.add(x,x,1);
seg2.addRound(x+1,x+k-1,-1);
}
int x = seg2.SEG[0].se;
seg2.add(x,x,-INF);
seg2.addRound(x+1,x+k-1,1);
seg1.addRound(x+n-k+1,x+n-1,1);
h[x] = h[x+n] = i;
htoi[i] = x;
}
htoi[END] = END;
// calculate next up
{
nxtUp[END][0] = END;
segH.build();
REV(i,0,n) {
int x = htoi[i];
segH.set(x,i);
segH.set(x+n,i);
int nxt = htoi[segH.get(x+1,x+k)];
if(nxt < x) nxt += n;
nxtUp[x ][0] = nxt;
nxtUp[x+n][0] = min(END,nxt+n);
}
}
// calculate next do
{
nxtDo[END][0] = END;
segH.build(-1);
REP(i,0,n) {
int x = htoi[i];
segH.set(x,-i);
segH.set(x+n,-i);
int res = -segH.get(x+1,x+k);
int nxt = (res >= 0 ? htoi[res] : END);
if(nxt < x) nxt += n;
nxtDo[x ][0] = nxt;
nxtDo[x+n][0] = min(END,nxt+n);
}
}
REP(j,1,20) {
RE(i,n*2+1) {
nxtDo[i][j] = nxtDo[nxtDo[i][j-1]][j-1];
nxtUp[i][j] = nxtUp[nxtUp[i][j-1]][j-1];
}
}
return;
}
int getNextUp(int i, int j) {
RE(x,20) if(j&(1<<x)) i = nxtUp[i][x];
return i;
}
int getNextDo(int i, int j) {
RE(x,20) if(j&(1<<x)) i = nxtDo[i][x];
return i;
}
int comp(int x, int y) {
if(h[x] < h[y]) {
int lb=0, ub=n;
while(lb != ub) {
int mid=(lb+ub)/2;
if(getNextUp(x,mid)+k-1 >= y) ub=mid;
else lb=mid+1;
}
int i = getNextUp(x,lb);
if(i != END && i+k-1 >= y && h[i] <= h[y]) return -1;
return 0;
} else {
int lb=0, ub=n;
while(lb != ub) {
int mid=(lb+ub)/2;
if(getNextDo(x,mid)+k-1 >= y) ub=mid;
else lb=mid+1;
}
int i = getNextDo(x,lb);
if(i != END && i+k-1 >= y && h[i] >= h[y]) return 1;
return 0;
}
}
int compare_plants(int x, int y) {
int res = comp(x,y);
if(res != 0) return res;
return -comp(y,x+n);
}
Compilation message
plants.cpp: In function 'void init(int, vi)':
plants.cpp:133:22: error: no matching function for call to 'SegMin::build(int)'
133 | segH.build(-1);
| ^
plants.cpp:73:10: note: candidate: 'void SegMin::build()'
73 | void build() {
| ^~~~~
plants.cpp:73:10: note: candidate expects 0 arguments, 1 provided
