P5138 题解

因为本题的代码难度远大于解法的思考，因此这里提供一种好写的写法。

做法不再赘述，就是转化为 \(depth\) 差以后上线段树分别维护两个信息以后求和。题解中大多数使用同一个线段树维护两个信息，可读性并不高，且比较难写。

事实上我们注意到两棵线段树仅有初始的信息不一样，剩下需要支持的操作完全一样，这启发我们通过一些方式让我们方便的写两棵线段树。

这里介绍一种广为人知的黑科技：在结构体中使用函数指针。具体的，本人使用的部分代码如下：

int (*func)(int);
void build(int p, int l, int r) {
    // printf("%d %d %d\n", p, l, r);
    if (l == r) {
        val[p] = func(l) % mod;
        return;
    }
    build(ls, l, mid), build(rs, mid + 1, r);
    val[p] = val[ls] + val[rs];
    val[p] %= mod;
}

那么，我们初始化两棵线段树，需要对 \(func\) 赋值：

st1.func = [](int x) { return calcfib(depth[rev[x]]); };
st2.func = [](int x) { return calcfib(depth[rev[x]] - 1); };
st1.build(1, 1, n), st2.build(1, 1, n);

接着，我们重写两个函数以方便查询：

void update(int x, int y, int k) {
    st1.update(1, 1, n, x, y, calcfib(k + 1));
    st2.update(1, 1, n, x, y, calcfib(k));
}
int query(int x, int y) {
    return (st1.query(1, 1, n, x, y) + st2.query(1, 1, n, x, y)) % mod;
}

这样的代码个人认为要更优雅，可读性更好一些，避免了一堆结构体或 pair 的不便。
放上最后的代码。