#include "obstacles.h"
#include <cassert>
#include <cstdio>
#include <vector>
#include <set>
#include <map>
#include <queue>
using namespace std;
int lin[200005];
int col[200005];
int prefl[200005];
int aint[800005];
set<int>st;
map<int,int>mp;
int m;
vector<int>ev[200005];
void build(int node,int st,int dr)
{
if(st==dr)
{
aint[node]=col[st];
return;
}
int mij=(st+dr)/2;
build(node*2,st,mij);
build(node*2+1,mij+1,dr);
aint[node]=max(aint[node*2],aint[node*2+1]);
}
int query(int node,int st,int dr,int qst,int qdr)
{
if(st>dr || st>qdr || qst>dr || qst>qdr)
{
return 0;
}
if(qst<=st && dr<=qdr)
{
return aint[node];
}
int mij=(st+dr)/2;
return max(query(node*2,st,mij,qst,qdr),query(node*2+1,mij+1,dr,qst,qdr));
}
priority_queue<pair<int,pair<int,int> >>pq;
void addedge(int c1,int c2)
{
int cost=query(1,1,m,c1,c2);
pq.push({-cost,{c1,c2}});
}
void addevent(int col)
{
mp[col]=1;
st.insert(col);
if(st.size()>=2)
{
addedge(*prev(st.find(col)),col);
}
}
int sef[200005];
int find(int a)
{
if(sef[a]==a)
{
return a;
}
return sef[a]=find(sef[a]);
}
void merge(int a,int b)
{
sef[find(b)]=find(a);
}
void kill(int col)
{
if(mp[col]==0)
{
return;
}
mp[col]=0;
st.erase(st.find(col));
auto nxt=st.lower_bound(col);
if(nxt==st.end())
{
return;
}
if(nxt!=st.begin())
{
addedge(*prev(nxt),*nxt);
}
}
void mergecols(int a,int b)
{
if(mp[a]==1 && mp[b]==1)
{
merge(a,b);
if(col[a]>col[b])
{
swap(a,b);
}
kill(b);
}
}
void initialize(std::vector<int> T, std::vector<int> H)
{
int n=T.size();
m=H.size();
for(int i=1; i<=m; i++)
{
col[i]=H[i-1];
sef[i]=i;
}
build(1,1,m);
for(int i=1; i<=n; i++)
{
lin[i]=T[i-1];
}
prefl[1]=lin[1];
for(int i=2; i<=n; i++)
{
prefl[i]=min(prefl[i-1],lin[i]);
}
for(int i=1; i<=m; i++)
{
if(col[i]<lin[1])
{
int st=1,dr=n;
while(st<=dr)
{
int mij=(st+dr)/2;
if(col[i]<prefl[mij])
{
st=mij+1;
}
else
{
dr=mij-1;
}
}
ev[dr+1].push_back(i);
addevent(i);
}
}
for(int i=1;i<=n;i++)
{
while(pq.size() && -pq.top().first<lin[i])
{
auto curr=pq.top();
pq.pop();
mergecols(curr.second.first,curr.second.second);
}
for(auto x:ev[i])
{
kill(x);
}
}
}
bool can_reach(int L, int R, int S, int D)
{
if(find(S+1)==find(D+1))
{
return true;
}
return false;
}
