「OI笔记」2021.8.16

Last updated on June 19, 2024 am

Day7

上午

P4074 糖果公园

  树上带修莫队,在一期夏令营的时候没有解决,而是直接淦SP10707,就是因为糖果公园这道题带修,而那时刚刚学莫队,不太熟练。今天上午就再次学习树上莫队,然后搞掉这道题。   树上莫队的核心就是将一棵树通过欧拉序变成一条链,从而转变而在链上的操作。当然,由于欧拉序的一些特性,我们需要对LCA做一些特殊工作。我习惯用树剖来求LCA。   在树剖的时候我们可以一起吧欧拉序给求了,然后考虑特殊情况。经过模拟,我们发现若起点不是两个节点的LCA的话,在欧拉序上是不会把LCA的贡献个算进去的。所以就要手动把LCA给怼进去。

下午

  下午搞主席树,像这种可持久化的东西我一直都不是很懂。今天再次学习,感觉和动态开点线段树很像。其实build和que操作和动态开点线段树应该是一样的,就是在update中有更改左右儿子的动作(语言不清。

1
2
3
4
5
6
7
8
9
10
11
int update(int k, int l, int r, int root) {  // 插入操作
int dir = ++tot;
ls[dir] = ls[root], rs[dir] = rs[root], sum[dir] = sum[root] + 1;
if (l == r) return dir;
int mid = l + r >> 1;
if (k <= mid)
ls[dir] = update(k, l, mid, ls[dir]);
else
rs[dir] = update(k, mid + 1, r, rs[dir]);
return dir;
}

还有就是,主席树的空间是要开到

[N<<5]

这好像也是动态开点线段树的大小吧(雾

晚上

  晚上去折腾克鲁斯卡尔重构树,也就是P4197 Peaks 有了主席树的基础,这道题明显就好搞多了。 今天的做题记录:

撒花~


「OI笔记」2021.8.16
https://www.qwqwq.com.cn/oi-note/2021-8-16/
Author
Stephen Zeng
Posted on
August 16, 2021
Licensed under