CSP-S 2021 游记
2021.10.22 来到杭州，然后打印乱七八糟的东西，吃了兰州拉面 ？？？ 晚上睡不着。 2021.10.23 早上 $5:00$ 就起来划水，上午普及组打铁。 $2h$ 打完四道暴力，然后开始扫雷（ 。 预估得分：$355$ ； 中午吃完饭就快一点半了，很困。 下午更困了屮。 $14:00$ 进场，趴着睡了 $20min$ 。 $14:30$ 开考，还是有点混乱，甚至想上大号。 看 $T1$ ，好像可做，$30min$ 打了个离散化 + 三分的做法，过了大样例，然后莫名自信 (垃圾大样例)。 然后看 $T2$ ,看半天不会打，看 $T3 T4$ 好像也不会。 $16:30$ 硬着头皮打 $T2$ 暴力，然后忽然发现 $T3$ 好像可做。 $17:00$ 发现根本想不出来，然后..
主席树学习笔记
权值线段树 就是指线段树的叶子节点保存的是当前值的个数。 权值线段树一般支持以下三个操作： insert erase/remove query 贴一个alphadalao的题解。 主席树 主席树，也叫做可持久化线段树，准确来说，应该叫做可持久化权值线段树，因为其中的每一颗树都是一颗权值线段树。 经典例题：查询区间第k小。 主席树是静态的。 为了实现可持久化，就要保存树的历史版本。最自然的想法当然是每进行一次修改，就新建一颗线段树，这样的空间复杂度显然是不能够接受的。通过观察不难发现，每次进行单点修改，发生变化的只有从叶子节点到根节点这一条链上的节点，换句话说，只有 $logN$ 个节点发生了变化，而其他的节点都可以重用，没有必要新建。 看图非常好理解。 超棒的讲解 然后就是一些实现上..
P7746 PLAĆE 题解
题目大意 给定一棵初始权值已知的树，每次操作: 对某个节点子树上的所有节点加上 $ x $ 。 查询某个节点的权值。 具体思路 1.暴力(112 pts) 对于每次修改操作，我们把修改值储存下来，然后每次询问操作我们历遍所求点的祖先，计算总和。 这看起来是 $\mathcal{O}( m\log n )$ 的正解，但是这仅限于这棵树是平衡的时候。在退化成链的极限条件下会被卡到 $\mathcal{O}( mn )$ ，在 $ 1 \le n , m , \le 5 \times 10^5 $ 的数据范围下会T掉。 核心代码： int a=read(); int x=tree[a].fa,w=tree[a].num; while(1){ if(x==0) break; w+=tag[x]; ..