这是本文档旧的修订版!
动态点分治
题目大意是给一棵树,然后每个节点会进行黑白染色,求某个时刻,树上最远的两个黑点的距离.
算是动态点分入门题,对于每个点维护两个可删堆来统计答案.每一次修改点的颜色的时候,修改一下点分树中对应的链上每个点的信息就行了.
可删堆的实现比较有意思,是用两个priority_queue封装在一起,一个记录所有元素,一个记录删除了的元素来实现.
Atcoder::AIsing Programming Contest 2020-F
https://atcoder.jp/contests/aising2020/tasks/aising2020_f
题意
求解一个过程看起来简单但繁琐的计数问题
题解
分输入的奇偶分别插值,得到通项
吐槽
插值是真的尝试了,分奇偶是真的第五层