题意：初始有n棵树，每棵树都只有1个n号节点，现在有m次添加操作，每次操作是将$[l,r]$范围内的树的$u$节点后面添加一个$v$节点。每个v节点只会被添加一次。
然后是q次询问，输出$[l,r]$范围内的树$x$节点的子树大小之和。
思路：由于每个节点被当成子节点添加到树上只会被添加一次，所以假设直接将节点连到一棵树上，按照dfs排序之后，x节点的子树dfs序必定是连续的。
考虑主席树，我们以dfs序为主席树的版本，每个节点就让$(ql，qr)$之间的树加一，最后只需要将ou[x]和in[x]-1这两个版本之间的主席树相减即可。（代码在最下方）
另一个做法：考虑扫描线，我们还是先处理处dfs序，对于节点x的求解，我们可以分解成，减去x之前所有节点(ql,qr)的值，再加上ou[x]的(ql,qr)的值，就得到了我们要的答案。所以我们还是按dfs序处理线段树，将每一个节点的影响加入线段树后，再处理这个节点需要加减的地方即可。我自己没有写过扫描线版本，此处引用一位朋友的代码。
//这是扫描线的关键，此处的线段树就是一个普通的区间求和的线段树。
scanf("%d", &q); for(int i = 1; i <= q; i++) { int x, l, r; scanf("%d%d%d", &x, &l, &r); V[in[x] - 1].push_back(Qus{-1, l, r, i}); V[ot[x]].push_back(Qus{1, l, r, i}); } for(int i = 1; i <= idx; i++) { Tree.update(L[rk[i]], R[rk[i]], 1, 1, n, 1); for(auto t : V[i]) { ans[t.id] += t.op * Tree.query(t.l, t.r, 1, n, 1); } }
#include<bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<=b;i++) #define dep(i,b,a) for(int i=b;i>=a;i--) #define clr(a,b) memset(a,b,sizeof(a)) #define pb push_back #define pii pair<int,int > using namespace std; typedef long long ll; ll rd() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } const int maxn=300010; const int inf=0x3f3f3f3f; int n,m,q,tot,root[maxn],l[maxn],r[maxn],in[maxn],ou[maxn],re[maxn],ti; struct node{ int l,r; ll sum,lazy; }tr[maxn*65]; vector<int >ve[maxn]; void dfs(int u){ in[u]=++ti; re[ti]=u; for(auto it:ve[u]){ dfs(it); } ou[u]=ti; } void update(int &rt,int pre,int l,int r,int ql,int qr,ll val){ tr[rt=++tot]=tr[pre]; tr[rt].sum+=(qr-ql+1)*val; if(ql<=l&&r<=qr){ tr[rt].lazy+=val; return; } int mid=(l+r)>>1; if(ql<=mid)update(tr[rt].l,tr[pre].l,l,mid,ql,min(qr,mid),val); if(mid<qr)update(tr[rt].r,tr[pre].r,mid+1,r,max(mid+1,ql),qr,val); } ll query(int rt,int pre,int l,int r,int ql,int qr,ll add){ if(ql<=l&&r<=qr){ return tr[rt].sum-tr[pre].sum+(r-l+1)*add; } add+=tr[rt].lazy-tr[pre].lazy; int mid=(l+r)>>1; ll res=0; if(ql<=mid)res+=query(tr[rt].l,tr[pre].l,l,mid,ql,qr,add); if(mid<qr)res+=query(tr[rt].r,tr[pre].r,mid+1,r,ql,qr,add); return res; } int main(){ cin>>n>>m; l[1]=1,r[1]=n; for(int i=1;i<=m;i++){ int u,v,x,y; u=rd(),v=rd(),x=rd(),y=rd(); ve[u].pb(v); l[v]=x,r[v]=y; } dfs(1); for(int i=1;i<=ti;i++){ int u=re[i]; update(root[i],root[i-1],1,n,l[u],r[u],1); } cin>>q; rep(i,1,q){ int x,ql,qr; x=rd(),ql=rd(),qr=rd(); printf("%lld ",query(root[ou[x]],root[in[x]-1],1,n,ql,qr,0)); } }