关于 LCT 实现 DDP 的问题
  • 板块学术版
  • 楼主smarthehe
  • 当前回复1
  • 已保存回复1
  • 发布时间2020/8/4 14:25
  • 上次更新2023/11/6 21:20:11
查看原帖
关于 LCT 实现 DDP 的问题
103732
smarthehe楼主2020/8/4 14:25

DDP 模板,定义

g(x,0)=xson(x)max{f(v,0),f(v,1)}g(x,0)= \sum_{x\neq son(x)}\max\{f(v,0),f(v,1)\}

g(x,1)=vson(x)f(v,0)+axg(x,1)=\sum\limits_{v\neq son(x)}f(v,0)+a_x

那么在 access\text{access} 的时候,由于改变虚实,需要改变 gg,照理来说应该需要对应的 ff 值。

但是,如下是日报的实现:

// access按照维护虚子树信息的方法写
inline void access(int x) {
    for (int y = 0; x; x = fa[y = x]) {
        splay(x);
        // 原来的右孩子由实变虚,要将它的贡献计入g
        if (ch[x][1]) {
            val[x].data[0][0] += std::max(prd[ch[x][1]].data[0][0], prd[ch[x][1]].data[1][0]);
            val[x].data[1][0] += prd[ch[x][1]].data[0][0];
        }
        // y变成了实儿子,要将它的贡献从g中减去。
        if (y) {
            val[x].data[0][0] -= std::max(prd[y].data[0][0], prd[y].data[1][0]);
            val[x].data[1][0] -= prd[y].data[0][0];
        }
        val[x].data[0][1] = val[x].data[0][0];
        ch[x][1] = y;
        update(x);
    }
}

直接调用儿子的矩阵,难道返回的不是 gg 值吗?

或者是有一些性质使得这里的 ggff 等价?

总之,蒟蒻在这卡住了……问了 luogu academic 群友也未能得解,先在这里求助qwq

2020/8/4 14:25
加载中...