「OI笔记」2021.8.16

Day7

¶上午

¶P4074 糖果公园

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

¶下午

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

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;
}