#include "obstacles.h"
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
int prnt[200005],cnt[200005];//DSU
int fix[200005],maxt[200005],maxt_n[200005],
mint[200005],mint_n[200005];
int sparseH[19][200005],sparseA[19][200005],spnomA[19][200005];
struct Gr{int A,nom;};
vector <Gr> gr;
Gr tmp;
int find_set(int u){
if (prnt[u]!=u) prnt[u]=find_set(prnt[u]);
return prnt[u];
}
void union_set(int u,int v){
u=find_set(u); v=find_set(v);
if (u==v) return;
if (cnt[v]>cnt[u]) swap(u,v);
cnt[u]+=cnt[v];
prnt[v]=u;
}
int getmaxH(int a, int b){
int len=b-a+1;
if (len==1) return sparseH[0][a];
int k=(int)log2(len-0.1);
return max(sparseH[k][a],sparseH[k][b+1-(1<<k)]);
}
int getnomA(int a, int b){
int len=b-a+1;
if (len==1) return spnomA[0][a];
int k=(int)log2(len-0.1);
int nom=spnomA[k][b+1-(1<<k)];
if (sparseA[k][a]>sparseA[k][b+1-(1<<k)])
nom=spnomA[k][a];
return nom;
}
void initialize(std::vector<int> T, std::vector<int> H) {
int n=T.size(),m=H.size();
for (int i=0;i<m;i++) {
prnt[i]=i; cnt[i]=1; //DSU init
if (H[i]<T[0]) fix[i]=1;//empty
sparseA[0][i]=-1; spnomA[0][i]=i;
sparseH[0][i]=H[i];
}
maxt[0]=T[0],maxt_n[0]=0;
mint[0]=T[0],mint_n[0]=0;
for (int i=1;i<n;i++){ //pref max,min of T
maxt[i]=maxt[i-1],maxt_n[i]=maxt_n[i-1];
if (T[i]>maxt[i-1])
maxt[i]=T[i],maxt_n[i]=i;
mint[i]=mint[i-1],mint_n[i]=mint_n[i-1];
if (T[i]<mint[i-1])
mint[i]=T[i],mint_n[i]=i;
}
//***************** 1 *****************
int nmin,hmin;
if (fix[0]==1) nmin=0,hmin=H[0];
for (int i=1;i<=m;i++)
if (fix[i]==1){
if (fix[i-1]==1) {
union_set(i,i-1);
if (H[i]<hmin) hmin=H[i],nmin=i;
} else hmin=H[i],nmin=i;
} else { // fix[i]==0
if (fix[i-1]){
//****** 2 find area of empty cells *******
int A=0,B=n-1,C;
while (A<B){
C=(A+B+1)/2;
if (mint[C]>hmin) A=C;
else B=C-1;
}
if (A>0) {
tmp.A=A, tmp.nom=nmin, gr.push_back(tmp);
sparseA[0][nmin]=A;
}
}//fix[i-1]==1
}//i
//****** Make sparse max tables *******
int k=log2(m-0.1);
for (int i=1;i<=k;i++){
int len=1<<i,len2=len>>1;
for (int j=0;j+len<=m;j++) {
sparseH[i][j]=max(sparseH[i-1][j],sparseH[i-1][j+len2]);
sparseA[i][j]=sparseA[i-1][j+len2]; spnomA[i][j]=spnomA[i-1][j+len2];
if (sparseA[i-1][j]>sparseA[i-1][j+len2]){
sparseA[i][j]=sparseA[i-1][j]; spnomA[i][j]=spnomA[i-1][j];
}
}//j
}//i
//********** last part of DSU ************
for (int i=0;i<(int)gr.size();i++){
int temp=maxt[gr[i].A], nom=gr[i].nom;
int height=maxt_n[gr[i].A];
int A,B,C;
// find ledft
if (i>0) {
A=0,B=nom;
while (A<B){
C=(A+B)/2;
int maxh=getmaxH(C,nom);
if (maxh>=temp) A=C+1;
else B=C;
}
if (A<nom) {
int nom2=getnomA(A,nom-1);
if (sparseA[0][nom2]>=height) union_set(nom,nom2);
}
}//i>0
// find right
if (i<(int)gr.size()-1){
A=nom,B=m-1;
while (A<B){
C=(A+B+1)/2;
int maxh=getmaxH(nom,C);
if (maxh>=temp) B=C-1;
else A=C;
}
if (A>nom) {
int nom2=getnomA(nom+1,A);
if (sparseA[0][nom2]>=height) union_set(nom,nom2);
}
}//i<sz-1
}//i
return;
}
bool can_reach(int L, int R, int S, int D) {
S=find_set(S); D=find_set(D);
return S==D;
}
