一道披着交互题外衣的传统题
题意就是在问
从出发，走编号内能达的点
和出发，走编号能达的点是否有交
显然可以把两点最大/小值作为边权建两颗重构树
倍增后就是在问两个子树是否有相同的叶子
转到序上就是对于2个排列
是否有公共点
两个排列看做二位坐标后就是简单扫描线了
#include<bits/stdc++.h>
#include "werewolf.h"
using namespace std;
#define cs const
#define re register
#define pii pair<int,int>
#define fi first
#define se second
#define ll long long
#define pb push_back
cs int RLEN=1<<20|1;
inline char gc(){
static char ibuf[RLEN],*ib,*ob;
(ib==ob)&&(ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin));
return (ib==ob)?EOF:*ib++;
}
inline int read(){
char ch=gc();
int res=0;bool f=1;
while(!isdigit(ch))f^=ch=='-',ch=gc();
while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=gc();
return f?res:-res;
}
template<class tp>inline void chemx(tp &a,tp b){a<b?a=b:0;}
template<class tp>inline void chemn(tp &a,tp b){a>b?a=b:0;}
int n,m,q;
cs int N=400005;
struct edge{
int u,v,w;
}e[N];
namespace Kruscal{
int val[N],in[N],out[N],ff[N],fa[N][19],lc[N],rc[N],tot,dfn;
inline int find(int x){
return ff[x]==x?x:ff[x]=find(ff[x]);
}
void dfs(int u){
for(int i=1;i<19;i++)fa[u][i]=fa[fa[u][i-1]][i-1];
if(u<=n)in[u]=out[u]=++dfn;
if(lc[u])dfs(lc[u]);
if(rc[u])dfs(rc[u]);
if(u>n){
in[u]=min(in[lc[u]],in[rc[u]]);
out[u]=max(out[lc[u]],out[rc[u]]);
}
}
inline void build(int *v){
while(tot){
ff[tot]=val[tot]=in[tot]=out[tot]=0;
for(int i=0;i<19;i++)fa[tot][i]=0;
lc[tot]=rc[tot]=0,tot--;
}
dfn=0;tot=n;
for(int i=1;i<=n;i++)ff[i]=i;
for(int i=1;i<=m;i++){
int f1=find(e[i].u),f2=find(e[i].v);
if(f1!=f2){
int f=++tot;
ff[f1]=ff[f2]=ff[f]=f;
val[f]=e[i].w;
lc[f]=f1,rc[f]=f2;
fa[f1][0]=fa[f2][0]=f;
}
}
// for(int i=1;i<=tot;i++)cout<<i<<" "<<val[i]<<" "<<lc[i]<<" "<<rc[i]<<'
';
dfs(tot);//cout<<fa[5][1]<<" "<<fa[5][0]<<'
';
for(int i=1;i<=n;i++)v[i]=in[i];//,cout<<i<<" "<<in[i]<<'
';
}
inline void getpos(int u,int l,int r,int &v1,int &v2,int kd){
if(u<l||u>r){v1=v2=0;return;}
if(kd==0){
for(int i=18;~i;i--){
if(val[fa[u][i]]>=l)u=fa[u][i];//,cerr<<u<<'
';
}
//cerr<<l<<" "<<r<<" "<<val[u]<<" "<<val[fa[u][0]]<<" "<<u<<'
';
v1=in[u],v2=out[u];
}
else{
for(int i=18;~i;i--){
if(fa[u][i]&&val[fa[u][i]]<=r)u=fa[u][i];
}//cerr<<l<<" "<<r<<" "<<val[u]<<" "<<val[fa[u][0]]<<" "<<u<<'
';
v1=in[u],v2=out[u];
}
}
}
inline bool comp1(cs edge &a,cs edge &b){
return a.w<b.w;
}
inline bool comp2(cs edge &a,cs edge &b){
return a.w>b.w;
}
int str[N],des[N],L[N],R[N];
int in[2][N],out[2][N],x[N],y[N];
int ans[N],tot;
vector<int>add[N];
struct ask{
int l,r,k,id;
ask(int a=0,int b=0,int c=0,int d=0):l(a),r(b),k(c),id(d){}
};
vector<ask>qq[N];
namespace Bit{
int tr[N];
#define lb(x) (x&(-x))
inline void update(int p){
for(;p<=n;p+=lb(p))tr[p]++;
}
inline int ask(int p,int res=0){
for(;p;p-=lb(p))res+=tr[p];return res;
}
inline int query(int l,int r){
return ask(r)-ask(l-1);
}
#undef lb
}
#define poly vector<int>
poly check_validity(int _n,poly X,poly Y,poly S,poly E,poly LL,poly RR){
n=_n,m=X.size(),q=S.size();
for(int i=1;i<=m;i++){
e[i].u=X[i-1]+1,e[i].v=Y[i-1]+1;
}
for(int i=1;i<=q;i++)str[i]=S[i-1]+1,des[i]=E[i-1]+1,L[i]=LL[i-1]+1,R[i]=RR[i-1]+1;
for(int i=1;i<=m;i++)e[i].w=min(e[i].u,e[i].v);
sort(e+1,e+m+1,comp2);
// cerr<<"OKk
";
Kruscal::build(x);
// cerr<<"Ok
";
for(int i=1;i<=q;i++){
Kruscal::getpos(str[i],L[i],n,in[0][i],out[0][i],0);
// cout<<i<<" "<<in[0][i]<<" "<<out[0][i]<<'
';
}
//cerr<<"Ok
";
for(int i=1;i<=m;i++)e[i].w=max(e[i].u,e[i].v);
sort(e+1,e+m+1,comp1);
Kruscal::build(y);
for(int i=1;i<=q;i++){
Kruscal::getpos(des[i],1,R[i],in[1][i],out[1][i],1);
//cout<<i<<" "<<in[1][i]<<" "<<out[1][i]<<'
';
}
for(int i=1;i<=n;i++)
add[x[i]].pb(y[i]);
for(int i=1;i<=q;i++){
qq[in[0][i]-1].pb(ask(in[1][i],out[1][i],-1,i));
qq[out[0][i]].pb(ask(in[1][i],out[1][i],1,i));
}
for(int i=1;i<=n;i++){
for(int &x:add[i])
Bit::update(x);
for(ask &x:qq[i]){
ans[x.id]+=x.k*Bit::query(x.l,x.r);
}
}
poly ret;
for(int i=1;i<=q;i++)if(ans[i])ret.pb(1);else ret.pb(0);
return ret;
}