Stephen Horizon
Stephen Horizon

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

https://pro.goforit.top/stephen-zeng/img/master/202108161.png

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

[N<<5]

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

晚上

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

撒花~

https://gimg2.baidu.com/image_search/src=http%3A%2F%2F5b0988e595225.cdn.sohucs.com%2Fimages%2F20170917%2F9ab8f252a2ca4587a3391a6140bb3194.gif&refer=http%3A%2F%2F5b0988e595225.cdn.sohucs.com&app=2002&size=f9999,10000&q=a80&n=0&g=0n&fmt=jpeg?sec=1631710651&t=606337c0a23de229a9a05be7e552f12a

Stephen Zeng

文章作者

发表评论

textsms
account_circle
email

Stephen Horizon

「OI笔记」2021.8.16
Day7 上午 P4074 糖果公园   树上带修莫队,在一期夏令营的时候没有解决,而是直接淦SP10707,就是因为糖果公园这道题带修,而那时刚刚学莫队,不太熟练。今天上午就再次学习树上莫队…
扫描二维码继续阅读
2021-08-16