#include "obstacles.h" #include <iostream> #include <cmath> 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 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; 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; 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]){ 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 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)/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]>=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; }