这题能黑了是因为洛谷仅有的题解都是些滥用数据结构的解法么……（
考虑一棵广义线段树的形态，和定位区间所得的结点的性质。
对于定位区间 \([l,r]\) 的过程，可以考虑 \([l-1,l-1]\) 和 \([r+1,r+1]\) 对应的结点和它们的 LCA（分别设为 \(L,R,U\)）。
注意到定位出来的区间都是 \(L\) 到 \(U\) 左儿子链上所有结点的在链以外的右儿子和 \(R\) 到 \(U\) 右儿子链上所有结点的在链以外的左儿子。
那么问题便是算 \(u\) 与这些结点的距离和。
不难想到转化为深度和减去 \(2\) 倍的 LCA 的深度和。
显然地，可以离线下来，暴力地使用数据结构 \(O((n+m) \log^2 n)\) 或 \(O((n+m)\log n)\) 维护（
实际上没必要，因为这些结点具有比较优美的性质，所以可以通过分类讨论解决。
若 \(u\) 不在 \(U\) 的子树内或恰为 \(U\)，则显然这些结点与 \(u\) 的 LCA 即为 \(u\) 与 \(U\) 的 LCA。
若 \(u\) 在 \(U\) 的左子树内，设 \(u\) 与 \(L\) 的 LCA 为 \(x\)，则 \(U\) 右子树内与 \(u\) 的 LCA 均为 \(U\)；左子树中 \(x\) 以下的结点与 \(u\) 的 LCA 显然为 \(x\)，而 \(x\) 至 \(U\) 的左儿子段都是 \(u\) 的祖先。
注意特判 \(u\) 在 \(x\) 的右子树内的情况，此时 LCA 应为 \(x\) 的右儿子。
若 \(u\) 在 \(U\) 的右子树内，与前一情况类似。
线性预处理出每个结点到根链上在链以外的左 / 右儿子个数和深度和即可。
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
using namespace std;
const int N = 4e5 + 3;
const int LG = 19;
int n,m,tot;
int pos[N + 5],rt;
int ch[N + 5][2],dep[N + 5],fa[N + 5],sz[N + 5],id[N + 5];
int f[LG + 5][N + 5];
int cnt[N + 5][2];
long long sum[N + 5][2];
int build(int l,int r)
{
int p = ++tot;
if(l == r)
return pos[l] = p;
int mid;
scanf("%d",&mid);
ch[p][0] = build(l,mid),
ch[p][1] = build(mid + 1,r);
return p;
}
void dfs1(int p)
{
static int tot = 0;
id[p] = ++tot,sz[p] = 1;
for(register int i = 1;i <= LG;++i)
f[i][p] = f[i - 1][f[i - 1][p]];
for(register int i = 0;i <= 1;++i)
if(ch[p][i])
fa[ch[p][i]] = f[0][ch[p][i]] = p,
dep[ch[p][i]] = dep[p] + 1,
dfs1(ch[p][i]),
sz[p] += sz[ch[p][i]];
}
void dfs2(int p)
{
for(register int i = 0;i <= 1;++i)
if(ch[p][i])
{
for(register int j = 0;j <= 1;++j)
cnt[ch[p][i]][j] = cnt[p][j],
sum[ch[p][i]][j] = sum[p][j];
if(ch[p][i ^ 1])
++cnt[ch[p][i]][i ^ 1],
sum[ch[p][i]][i ^ 1] += dep[ch[p][i ^ 1]];
dfs2(ch[p][i]);
}
}
inline int getlca(int x,int y)
{
if(dep[x] < dep[y])
swap(x,y);
for(register int i = LG;~i;--i)
if(dep[f[i][x]] >= dep[y])
x = f[i][x];
if(x == y)
return x;
for(register int i = LG;~i;--i)
if(f[i][x] ^ f[i][y])
x = f[i][x],y = f[i][y];
return fa[x];
}
long long ans;
int main()
{
scanf("%d",&n),build(1,n);
rt = ++tot,
ch[rt][0] = pos[0] = ++tot,ch[rt][1] = 1;
rt = ++tot,
ch[rt][0] = rt - 2,ch[rt][1] = pos[n + 1] = ++tot;
dep[rt] = 1,dfs1(rt),dfs2(rt);
scanf("%d",&m);
for(int u,l,r,lca,x,ls,rs;m;--m)
{
scanf("%d%d%d",&u,&l,&r),
lca = getlca(l = pos[l - 1],r = pos[r + 1]),ls = ch[lca][0],rs = ch[lca][1],
ans = (sum[l][1] - sum[ls][1] + sum[r][0] - sum[rs][0]) + (long long)dep[u] * (cnt[l][1] - cnt[ls][1] + cnt[r][0] - cnt[rs][0]);
if(id[u] <= id[lca] || id[u] >= id[lca] + sz[lca])
x = getlca(u,lca),
ans -= 2LL * dep[x] * (cnt[l][1] - cnt[ls][1] + cnt[r][0] - cnt[rs][0]);
else if(id[u] >= id[ls] && id[u] < id[ls] + sz[ls])
x = getlca(u,l),
ans -= 2LL * dep[lca] * (cnt[r][0] - cnt[rs][0]),
ans -= 2LL * dep[x] * (cnt[l][1] - cnt[x][1]),
ans -= 2LL * ((sum[x][1] - sum[ls][1]) - (cnt[x][1] - cnt[ls][1])),
id[u] >= id[ch[x][1]] && id[u] < id[ch[x][1]] + sz[ch[x][1]] && (ans -= 2);
else
x = getlca(u,r),
ans -= 2LL * dep[lca] * (cnt[l][1] - cnt[ls][1]),
ans -= 2LL * dep[x] * (cnt[r][0] - cnt[x][0]),
ans -= 2LL * ((sum[x][0] - sum[rs][0]) - (cnt[x][0] - cnt[rs][0])),
id[u] >= id[ch[x][0]] && id[u] < id[ch[x][0]] + sz[ch[x][0]] && (ans -= 2);
printf("%lld\n",ans);
}
}