题目分析

处理广义线段树的一类套路方法。

首先，定义原来的线段树为原树，并且将其改造一下，使得它能够管理的区间为 $[0,n+1]$。

定义左偏树（跟一种可并堆重名了 2333）为一棵将原树上，所有是左儿子的点提取出来，构成的一棵树，每个点的父亲，是代表在其左边，与其代表区间相邻的区间，且深度比它浅的节点。画出来是这样的：

定义右偏树为提取右儿子们，与在它右边深度比它浅的第一个节点相连的树。

左偏树可以在遍历原树时，开个栈，每次先将当前点的左儿子与栈顶元素相连，然后将当前点左儿子压入栈，遍历当前点右子树，再将左儿子弹出栈，再遍历左子树，如此得到。右偏树类似。

接下来，对于一个询问 $(x,l,r)$，首先找到代表区间 $[l-1,l-1]$的点 $k_1$和代表区间 $[r+1,r+1]$的点 $k_2$（这也就是要改造原树使它能够控制区间 $[0,n+1]$的原因），然后求出它们的 LCA，点 $o$。

不难发现，$k_1$到 $o$的路径上经过的所有点，若它的右儿子没被经过，则右儿子在 $S_{[l,r]}$中，并且这些点还对应了一条右偏树上的链。从 $k_2$到 $o$路径上，那些点的左儿子也有类似的性质。

若 $k_1$为一个左儿子，则这条右偏树上链最深点为它的兄弟。若它是右儿子，则最深点为其在右偏树上的父亲。而最浅点的父亲为 $o$的右儿子。（$k_2$部分类似，略过）

若 dfs 一次右偏树，每进入一个点 $x$，序列末尾加一个元素 $+x$，表示处理序列一个前缀处理到此，要将 $x$加入集合。离开 $x$时，加入 $-x$，表示要将 $x$从集合中 ban 掉。那么一个询问在右偏树上构成的那条链，就是最深点的正位置的前缀操作一遍剩下的集合的贡献，减去最浅点父亲正位置的集合的前缀贡献。

于是我们将询问离线，顺序处理，每次维护一个前缀的贡献，然后再加加减减就可以得到答案了。

而询问 $(x,l,r)$要问的东西等价于问

$$dep_x|S_{[l,r]}|+\sum_{y \in S_{[l,r]}} dep_y-2\sum_{y \in S_{[l,r]}} dep_{lca(x,y)}$$

前两项只要维护当前集合的元素个数和元素 $dep$和即可，很简单，后一项呢？

也不难，每将一个 $y$加入集合，就在所有 $y$的祖先处把一个标记+1，ban 掉时-1，则 $x$的所有祖先的标记和，就是 lca 的深度和。可以用树链剖分＋线段树维护。

代码

#include<bits/stdc++.h>
using namespace std;
#define RI register int
int read() {
    int q=0;char ch=' ';
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') q=q*10+ch-'0',ch=getchar();
    return q;
}
typedef long long LL;
const int N=400010;
int n,m,SZ_A,rt_A,st_top,js1,js2,tim;
int son[N][2],fa[N],st[N],pos[N],dep[N],sz[N],top[N],dfn[N];LL ans[N];
struct node{int p,x,v,id;}q1[N<<1],q2[N<<1];
bool cmp(node A,node B) {return A.p<B.p;}

struct segment_tree{
    LL sum[N<<2],lz[N<<2];
    void build(int s,int t,int i) {
        sum[i]=lz[i]=0;if(s==t) return;
        int mid=(s+t)>>1;
        build(s,mid,i<<1),build(mid+1,t,(i<<1)|1);
    }
    void put_lz(int s,int t,int i,int v) {lz[i]+=v,sum[i]+=1LL*(t-s+1)*v;}
    void pd(int s,int t,int i) {
        int mid=(s+t)>>1;
        put_lz(s,mid,i<<1,lz[i]),put_lz(mid+1,t,(i<<1)|1,lz[i]),lz[i]=0;
    }
    void modify(int l,int r,int s,int t,int i,int v) {
        if(l<=s&&t<=r) {put_lz(s,t,i,v);return;}
        int mid=(s+t)>>1;if(lz[i]) pd(s,t,i);
        if(l<=mid) modify(l,r,s,mid,i<<1,v);
        if(mid+1<=r) modify(l,r,mid+1,t,(i<<1)|1,v);
        sum[i]=sum[i<<1]+sum[(i<<1)|1];
    }
    LL query(int l,int r,int s,int t,int i) {
        if(l<=s&&t<=r) return sum[i];
        int mid=(s+t)>>1;LL re=0;if(lz[i]) pd(s,t,i);
        if(l<=mid) re=query(l,r,s,mid,i<<1);
        if(mid+1<=r) re+=query(l,r,mid+1,t,(i<<1)|1);
        return re;
    }
}ST;
void walk(int x,int v)
    {while(x) ST.modify(dfn[top[x]],dfn[x],1,SZ_A,1,v),x=fa[top[x]];}
LL q_walk(int x) {
    LL re=0;
    while(x) re+=ST.query(dfn[top[x]],dfn[x],1,SZ_A,1),x=fa[top[x]];
    return re;
}

struct Tree{
    int h[N],ne[N],to[N],p[N],pos[N],fa[N],tot,js;
    void add(int x,int y) {to[++tot]=y,ne[tot]=h[x],h[x]=tot;}
    void build(int x,int o) {
        if(!son[x][0]&&!son[x][1]) return;
        fa[son[x][o]]=st[st_top],add(st[st_top],son[x][o]),st[++st_top]=son[x][o];
        build(son[x][o^1],o),--st_top,build(son[x][o],o);
    }
    void dfs(int x) {
        p[++js]=x,pos[x]=js;
        for(RI i=h[x];i;i=ne[i]) dfs(to[i]);
        p[++js]=-x;
    }
    void work(node *q,int qjs) {
        sort(q+1,q+1+qjs,cmp),ST.build(1,SZ_A,1);
        LL now_sumd=0,now_sum=0;
        for(RI i=1,j=1;i<=js;++i) {
            if(p[i]<0) now_sumd-=dep[-p[i]],--now_sum,walk(-p[i],-1);
            else now_sumd+=dep[p[i]],++now_sum,walk(p[i],1);
            while(j<=qjs&&q[j].p==i) {
                LL tmp=now_sumd+now_sum*(LL)dep[q[j].x]-2*q_walk(q[j].x);
                ans[q[j].id]+=q[j].v*tmp,++j;
            }
        }
    }
}lT,rT;

void build_A(int &x,int s,int t) {
    x=++SZ_A;if(s==t) {pos[s]=x;return;}
    int mid=read();
    build_A(son[x][0],s,mid),build_A(son[x][1],mid+1,t);
}
void dfs1(int x,int las) {
    sz[x]=1,fa[x]=las,dep[x]=dep[las]+1;
    if(son[x][0]) dfs1(son[x][0],x),sz[x]+=sz[son[x][0]];
    if(son[x][1]) dfs1(son[x][1],x),sz[x]+=sz[son[x][1]];
}
void dfs2(int x) {
    dfn[x]=++tim;if(!son[x][0]&&!son[x][1]) return;
    if(sz[son[x][0]]>sz[son[x][1]]) {
        top[son[x][0]]=top[x],dfs2(son[x][0]);
        top[son[x][1]]=son[x][1],dfs2(son[x][1]);
    }
    else {
        top[son[x][1]]=top[x],dfs2(son[x][1]);
        top[son[x][0]]=son[x][0],dfs2(son[x][0]);
    }
}
int lca(int x,int y) {
    while(top[x]!=top[y]) dep[top[x]]>dep[top[y]]?x=fa[top[x]]:y=fa[top[y]];
    return dep[x]<dep[y]?x:y;
}
int is(int x) {return son[fa[x]][1]==x;}

int main()
{
    n=read();
    build_A(rt_A,1,n);
    ++SZ_A,son[SZ_A][0]=rt_A;
    ++SZ_A,son[SZ_A-1][1]=SZ_A,pos[n+1]=SZ_A;
    ++SZ_A,son[SZ_A][1]=SZ_A-2,rt_A=SZ_A;
    ++SZ_A,son[SZ_A-1][0]=SZ_A,pos[0]=SZ_A;
    dfs1(rt_A,0),top[rt_A]=rt_A,dfs2(rt_A);
    st[++st_top]=rt_A,lT.build(rt_A,0),rT.build(rt_A,1);
    lT.dfs(rt_A),rT.dfs(rt_A);
    m=read();
    for(RI i=1;i<=m;++i) {
        int x=read(),l=read(),r=read();
        int k1=pos[l-1],k2=pos[r+1],o=lca(k1,k2);
        q1[++js1]=(node){lT.pos[son[o][0]],x,-1,i};
        if(is(k2)) q1[++js1]=(node){lT.pos[son[fa[k2]][0]],x,1,i};
        else q1[++js1]=(node){lT.pos[lT.fa[k2]],x,1,i};
        q2[++js2]=(node){rT.pos[son[o][1]],x,-1,i};
        if(is(k1)) q2[++js2]=(node){rT.pos[rT.fa[k1]],x,1,i};
        else q2[++js2]=(node){rT.pos[son[fa[k1]][1]],x,1,i};
    }
    lT.work(q1,js1),rT.work(q2,js2);
    for(RI i=1;i<=m;++i) printf("%lld\n",ans[i]);
    return 0;
}