### Idea

$E_i$ 那部分同理。

### Code

#include <bits/stdc++.h>
#define maxn 200100
using namespace std;
int x=0,flag=1;char ch=getchar();
while(!isdigit(ch)&&ch!='-') ch=getchar();
if (ch=='-') flag=-1,ch=getchar();
while(isdigit(ch)) x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x*flag;
}
struct Edge{
int to,next;
Edge(int a=0,int b=0){
to=a,next=b;
}
};
Edge raw_edge[maxn<<2];
int cnt,n,m,q;
void Raw_Add(int a,int b){
}
struct Tree{
Edge l[maxn<<2];
int cnt,tot,tim,dft;
int p[20][maxn],fa[maxn];
int find(int x){
return fa[x]==x?x:fa[x]=find(fa[x]);
}
void Add(int a,int b){
}
void Kruskal(){
for (int i=1;i<=n;++i)
fa[i]=i;
if (dft) for (int u=n;u;--u){
int v=raw_edge[i].to;if (v>u){
int fx=find(u),fy=find(v);
if (fx==fy) continue;
if (++tot==n-1) return;
}
}
}
else for (int u=1;u<=n;++u){
int v=raw_edge[i].to;if (v<u){
int fx=find(u),fy=find(v);
if (fx==fy) continue;
if (++tot==n-1) return;
}
}
}
}
void Dfs(int u,int f){
dfn[u]=++tim;
p[0][u]=f;
for (int i=1;i<20;++i)
p[i][u]=p[i-1][p[i-1][u]];
int v=l[i].to;if (v==f) continue;
Dfs(v,u);
}
low[u]=tim;
}
void Jump(int &u,int k){
if (dft) for (int i=19;~i;--i){
if (p[i][u]&&(p[i][u]>=k)) u=p[i][u];}
else for (int i=19;~i;--i)
if (p[i][u]&&p[i][u]<=k) u=p[i][u];
}
void Build(int mark){
dft=mark;Kruskal();
if (mark) Dfs(1,0);
else Dfs(n,0);
}
}Max,Min;
struct President_Tree{
#define mid ((l+r)>>1)
int cnt,rt[maxn],t[maxn<<6];
int ls[maxn<<6],rs[maxn<<6];
void Update(int &p,int pre,int l,int r,int x){
if (!p) p=++cnt;t[p]=t[pre]+1;
if (l==r) return;
if (mid>=x) rs[p]=rs[pre],Update(ls[p],ls[pre],l,mid,x);
else ls[p]=ls[pre],Update(rs[p],rs[pre],mid+1,r,x);
}
int Query(int lp,int rp,int l,int r,int L,int R){
if (L<=l&&r<=R) return t[rp]-t[lp];
if (mid>=R) return Query(ls[lp],ls[rp],l,mid,L,R);
if (mid<L) return Query(rs[lp],rs[rp],mid+1,r,L,R);
return Query(ls[lp],ls[rp],l,mid,L,R)+Query(rs[lp],rs[rp],mid+1,r,L,R);
}
}T;
int main(){
for (int i=1;i<=m;++i){
}
Max.Build(0),Min.Build(1);
for (int i=1;i<=n;++i)
val[Min.dfn[i]]=Max.dfn[i];
for (int i=1;i<=n;++i)
T.Update(T.rt[i],T.rt[i-1],1,n,val[i]);
for (int i=1;i<=q;++i){
}