#include "obstacles.h"
#include <iostream>
#include <cmath>
using namespace std;
int prnt[200000],cnt[200000];//DSU
int fix[200001],maxt[200000],maxt_n[200000],
mint[200000],mint_n[200000];
int sparseH[19][200000],sparseA[19][200000],spnomA[19][200000];
struct H{int h,ind;};
bool operator <(H a,H b){
return a.h<b.h;
};
bool operator ==(H a,H b){
return a.h==b.h;
};
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) {
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, 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, 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; sparseH[0][i]=H[i];
spnomA[0][i]=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;
}
//cout<<"A="<<A<<endl;
if (A>0) {
tmp.A=A, tmp.nom=nmin, gr.push_back(tmp);
sparseA[0][nmin]=A;
}
}//fix[i-1]==1
}//i
//+
//****** Make spase 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+len/2]){
sparseA[i][j]=sparseA[i-1][j]; spnomA[i][j]=spnomA[i-1][j];
}
}//j
}//i
//+
//********** last part of DSU ************
for (int i=1;i<(int)gr.size();i++){
int temp=gr[i].A, nom=gr[i].nom;
int A=0,B=nom,C;
while (A<B){
C=(A+B+1)/2;
int maxh=getmaxH(C,nom);
if (maxh>=temp) B=C-1;
else A=C;
}
int nom2=getnomA(A,nom-1);
if (sparseA[0][nom2]>=temp)
union_set(nom,nom2);
}//i
return;
}
bool can_reach(int L, int R, int S, int D) {
S=find_set(S); D=find_set(D);
return S==D;
}
