洛谷P5210 [ZJOI2017]线段树题解

题目链接：P5210 [ZJOI2017]线段树

题意：

线段树是九条可怜很喜欢的一个数据结构，它拥有着简单的结构、优秀的复杂度与强大的功能，因此可怜曾经花了很长时间研究线段树的一些性质。

最近可怜又开始研究起线段树来了，有所不同的是，她把目光放在了更广义的线段树上：在正常的线段树中，对于区间 $[l, r]$，我们会取 $m = \lfloor \frac{l+r}{2} \rfloor$，然后将这个区间分成 $[l, m]$ 和 $[m + 1, r]$ 两个子区间。在广义的线段树中，$m$ 不要求恰好等于区间的中点，但是 $m$ 还是必须满足 $l \le m < r$ 的。不难发现在广义的线段树中，树的深度可以达到 $O(n)$ 级别。

例如下面这棵树，就是一棵广义的线段树：

为了方便，我们按照先序遍历给线段树上所有的节点标号，例如在上图中，$[2, 3]$ 的标号是 $5$，$[4, 4]$ 的标号是 $9$，不难发现在 $[1, n]$ 上建立的广义线段树，它共有着 $2n − 1$ 个节点。

考虑把线段树上的定位区间操作 $($就是打懒标记的时候干的事情$)$ 移植到广义线段树上，可以发现在广义的线段树上还是可以用传统的线段树上的方法定位区间的，例如在上图中，蓝色节点和蓝色边就是在定位区间 $[2, 4]$ 时经过的点和边，最终定位到的点是 $[2, 3]$ 和 $[4, 4]$。

如果你对线段树不熟悉，这儿给出定位区间操作形式化的定义：给出区间 $[l, r]$，找出尽可能少的区间互不相交的线段树节点，使得它们区间的并集恰好是 $[l, r]$。

定义 $S_{[l,r]}$ 为定位区间 $[l, r]$ 得到的点集，例如在上图中，$S_{[2,4]} = \{5, 9\}$。定义线段树上两个点 $u, v$ 的距离 $d(u, v)$ 为线段树上 $u$ 到 $v$ 最短路径上的边数，例如在上图中 $d(5, 9) = 3$。

现在可怜给了你一棵 $[1, n]$ 上的广义的线段树并给了 $m$ 组询问，每组询问给出三个数 $u, l, r\ (l \le r)$，可怜想要知道 $\sum_{v \in S_{[l, r]}} d(u, v)$。

输入格式：

第一行输入一个整数 $n$。

接下来一行包含 $n - 1$ 个空格隔开的整数：按照标号递增的顺序，给出广义线段树上所有非叶子节点的划分位置 $m$。不难发现通过这些信息就能唯一确定一棵 $[1, n]$ 上的广义线段树。

接下来一行输入一个整数 $m$。

之后 $m$ 行每行输入三个整数 $u, l, r\ (1 \le u \le 2n − 1, 1 \le l \le r \le n)$，表示一组询问。

输出格式：

对于每组询问，输出一个整数表示答案。

数据范围：

对于 $100\%$ 的数据，保证 $2\le n \le 2\times 10^5, 1\le m \le 2\times 10^5$。

~~不得不说，这题有点东西的~~。

考虑如何快速定位区间 $[l,r]$ 。

我们可以找到 $[l-1,l-1]$ 和 $[r+1,r+1]$ 对应的结点以及他们的 LCA（记为 $L,R,U$ ）

注意到定位到的所有结点都是（以下两种之一）

「 $L$ 到 $U$ 左儿子的链上，所有结点的在链以外的右儿子」
「 $R$ 到 $U$ 右儿子的链上，所有结点的在链以外的左儿子」

现在的问题就是计算 $u$ 到这些结点的距离和。据说可以用离线+数据结构维护。

这里提供一种不需要离线+数据结构的做法，来自参考文献[1]

又到了分讨的环节。

若 $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$ 的右子树内，和情况2类似，不再叙述。

然后我们就只要预处理出每个结点的深度，求个 LCA 就好了

时间复杂度 $\mathcal{O}(n \log n)$

代码：

#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
#define ll long long
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
namespace FastIO
{
    #define gc() readchar()
    #define pc(a) putchar(a)
    #define SIZ (int)(1e6+15)
    char buf1[SIZ],*p1,*p2;
    char readchar()
    {
        if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
        return p1==p2?EOF:*p1++;
    }
    template<typename T>void read(T &k)
    {
        char ch=gc();T x=0,f=1;
        while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
        while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
        k=x*f;
    }
    template<typename T>void write(T k)
    {
        if(k<0){k=-k;pc('-');}
        static T stk[66];T top=0;
        do{stk[top++]=k%10,k/=10;}while(k);
        while(top){pc(stk[--top]+'0');}
    }
    template<typename T>void print(T x) { write(x); pc('\n'); }
}using namespace FastIO;
#define N ((int)(4e5+15))
#define L 20

int n,m,tot,rt,tim,pos[N],ch[N][2],dep[N];
int sz[N],id[N],fa[N][19],cnt[N][2],lg2[N];
ll res,sum[N][2];
#define ls(at) ch[at][0]
#define rs(at) ch[at][1]
int build(int l,int r)
{
    int at = ++tot;
    if(l == r) return pos[l] = at;
    int mid; read(mid);
    ls(at) = build(l, mid);
    rs(at) = build(mid + 1, r);
    return at;
}
void dfs1(int at)
{
    id[at] = ++tim; sz[at] = 1;
    for(int i=1; i<=lg2[dep[at]]; i++)
        fa[at][i] = fa[fa[at][i-1]][i-1];
    for(int t=0,x; t<2; t++) if(x = ch[at][t])
    {
        fa[x][0] = at;
        dep[x] = dep[at] + 1;
        dfs1(x); sz[at] += sz[x];
    }
}
void dfs2(int at)
{
    for(int t=0,x,y; t<2; t++) if(x = ch[at][t])
    {
        for(int i=0; i<2; i++)
        {
            cnt[x][i] = cnt[at][i];
            sum[x][i] = sum[at][i];
        }
        if(y = ch[at][t^1])
        {
            ++cnt[x][t^1];
            sum[x][t^1] += dep[y];
        }
        dfs2(x);
    }
}
int LCA(int x,int y)
{
    if(dep[x] < dep[y]) swap(x,y);
    while(dep[x] > dep[y]) x = fa[x][lg2[dep[x] - dep[y]] - 1];
    if(x == y) return x;
    for(int k=lg2[dep[x]]; ~k; k--)
        if(fa[x][k] != fa[y][k]) x = fa[x][k], y = fa[y][k];
    return fa[x][0];
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    read(n); build(1,n); lg2[1] = 1;
    for(int i=2; i<=n; i++) lg2[i] = lg2[i >> 1] + 1;
    rt = ++tot; ls(rt) = pos[0] = ++tot; rs(rt) = 1;
    rt = ++tot; ls(rt) = rt - 2; rs(rt) = pos[n+1] = ++tot;
    dep[rt] = 1; dfs1(rt); dfs2(rt);
    int Q; read(Q);
    for(int u,l,r,d,x; Q--; )
    {
        read(u); read(l); read(r);
        d = LCA(l = pos[l-1], r = pos[r+1]);
        // cout << d << '\n';
        res = (sum[l][1] - sum[ls(d)][1] + sum[r][0] - sum[rs(d)][0])
            + (ll)dep[u] * (cnt[l][1] - cnt[ls(d)][1] + cnt[r][0] - cnt[rs(d)][0]);
        // cout << "res = " << res << '\n';
        if(id[u] <= id[d] || id[u] >= id[d] + sz[d])
        {
            x = LCA(u,d);
            res -= 2ll * dep[x] * (cnt[l][1] - cnt[ls(d)][1] + cnt[r][0] - cnt[rs(d)][0]);
        }else if(id[u] >= id[ls(d)] && id[u] < id[ls(d)] + sz[ls(d)])
        {
            x = LCA(u,l);
            res -= 2ll * dep[d] * (cnt[r][0] - cnt[rs(d)][0]);
            res -= 2ll * dep[x] * (cnt[l][1] - cnt[x][1]);
            res -= 2ll * ((sum[x][1] - sum[ls(d)][1]) - (cnt[x][1] - cnt[ls(d)][1]));
            ((id[u] >= id[rs(x)]) && (id[u] < id[rs(x)] + sz[rs(x)])) ? (res -= 2) : 0;
        }else
        {
            x = LCA(u,r);
            res -= 2ll * dep[d] * (cnt[l][1] - cnt[ls(d)][1]);
            res -= 2ll * dep[x] * (cnt[r][0] - cnt[x][0]);
            res -= 2ll * ((sum[x][0] - sum[rs(d)][0]) - (cnt[x][0] - cnt[rs(d)][0]));
            ((id[u] >= id[ls(x)]) && (id[u] < id[ls(x)] + sz[ls(x)])) ? (res -= 2) : 0;
        }
        print(res);
    }
    return 0;
}