#include #define Add(x,y) (x+y>=mod)?(x+y-mod):(x+y) #define lowbit(x) x&(-x) #define pi pair #define pii pair> #define iip pair,ll> #define ppii pair,pair> #define fi first #define se second #define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x #define Full(a) memset(a,0,sizeof(a)) #define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout); using namespace std; typedef double db; typedef unsigned long long ull; typedef long long ll; bool Begin; const ll N=100100; inline ll read(){ ll x=0,f=1; char c=getchar(); while(c<'0'||c>'9'){ if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c<='9'){ x=(x<<1)+(x<<3)+(c^48); c=getchar(); } return x*f; } inline void write(ll x){ if(x<0){ putchar('-'); x=-x; } if(x>9) write(x/10); putchar(x%10+'0'); } struct Node{ ll l,r; ll len; ll L1,L2; ll R1,R2; bool F; Node(){ l=r=len=L1=L2=R1=R2=0; F=1; } void print(){ printf("len:%lld L1:%lld L2:%lld R1:%lld R2:%lld F:%lld\n",len,L1,L2,R1,R2,(ll)F); } }X[N<<2]; ll n,q,u,v,cnt,l; ll h[N],w[N],t[N],z[N],d[N],p[N],fa[N],dfn[N],id[N],W[N]; vector E[N]; bool check(ll a,ll b,ll c){ if(a==b||a==c||b==c) return 0; if(min({a,b,c})==b||max({a,b,c})==b) return 1; return 0; } void add(ll x){ if(!x) return ; h[++l]=x; } void add(Node a){ if(a.len==1) add(a.L1); else if(a.len==2) add(a.L1),add(a.R1); else if(a.len==3) add(a.L1),add(a.L2),add(a.R1); else add(a.L1),add(a.L2),add(a.R2),add(a.R1); } Node operator+(Node a,Node b){ if(!a.len) return b; if(!b.len) return a; l=0; Node ans; ans.l=a.l; ans.r=b.r; ans.len=a.len+b.len; add(a),add(b); ans.L1=h[1],ans.L2=h[2]; ans.R1=h[l],ans.R2=h[l-1]; if(ans.len<=2) ans.F=1; else{ if(ans.len==3) ans.F=check(h[1],h[2],h[3]); else{ ans.F=a.F&b.F; if(a.len>1) ans.F&=check(a.R2,a.R1,b.L1); if(b.len>1) ans.F&=check(a.R1,b.L1,b.L2); } } return ans; } Node rev(Node a){ swap(a.L1,a.R1); swap(a.L2,a.R2); return a; } void add(ll u,ll v){ E[u].push_back(v); E[v].push_back(u); } void dfs1(ll u,ll f){ p[u]=1; for(auto v:E[u]){ if(v==f) continue; fa[v]=u; d[v]=d[u]+1; dfs1(v,u); p[u]+=p[v]; if(p[v]>p[z[u]]) z[u]=v; } } void dfs2(ll u,ll k){ t[u]=k; dfn[u]=++cnt; id[cnt]=u; W[cnt]=w[u]; if(!z[u]) return ; dfs2(z[u],k); for(auto v:E[u]){ if(v==fa[u]||v==z[u]) continue; dfs2(v,v); } } void pushup(ll k){ X[k]=X[k<<1]+X[k<<1|1]; } void build(ll k,ll l,ll r){ X[k].l=l,X[k].r=r; X[k].len=r-l+1; if(l==r){ X[k].L1=X[k].R1=W[l]; X[k].F=1; return ; } ll mid=(l+r)>>1; build(k<<1,l,mid); build(k<<1|1,mid+1,r); pushup(k); } Node query(ll k,ll l,ll r){ if(X[k].l==l&&r==X[k].r) return X[k]; ll mid=(X[k].l+X[k].r)>>1; if(r<=mid) return query(k<<1,l,r); else if(l>mid) return query(k<<1|1,l,r); else return query(k<<1,l,mid)+query(k<<1|1,mid+1,r); } bool query(ll u,ll v){ bool f=0; Node a,b,h; while(t[u]!=t[v]){ if(d[t[u]]