P5311 [Ynoi2011] 成都七中 题意 给你一棵 \(n\) 个节点的树，每个节点有一种颜色，有 \(m\) 次查询操作。 查询操作给定参数 \(l\ r\ x\)，需输出： 将树中编号在 \([l,r]\) 内的所有节点保留，\(x\) 所在连通块中颜色种类数。 每次查询操作独立。 思路 考虑点分树的思想。假设我们已经建出点分树，对于每一个分治中心，我们应该...

P5468 [NOI2019] 回家路线 斜率优化入门（指我写的东西而不是这道题） 题意 \(n\) 个节点，有 \(m\) 趟列车，车 \(i\) 从 \(p_i\) 时刻至 \(q_i\) 时刻从 \(x_i\) 地到 \(y_i\) 地。猫猫需要只坐列车从 \(1\) 节点到达 \(n\) 节点。 设猫猫在一个地方等待的时间为 \(t\)，那么代价为 \(At^2+Bt+C\)...

P5350 序列 题意 维护一个序列，支持区间求和、赋值、加值、复制、交换、翻转操作，其中交换和复制操作保证两段区间长度相等且不交。答案对 \(1e9+7\) 取模。 思路 对于区间求和、赋值、加值、交换、翻转操作我们都可以很轻松地使用平衡树进行维护。所以现在的难点就在于复制操作：如何复制一段区间？ 如果我们暴力复制的话，每次我们不得不将被复制的子树扫一遍进行复制，这是肯定不行的...

P5591 小猪佩奇学数学 知识点 二项式定理 \[ (x+1)^n=\sum_{i=0}^n\binom nix^i \] 单位根反演 \[ [n\mid k]=\frac 1n\sum_{i=0}^{n-1}\omega_n^{ik} \] 证明： \[ [n\mid k]=\begin{cases}\frac 1n\sum_{i=0}^{n-1}\omega_n^...

P5471- K-D tree优化建图-弹跳 优化建图是一种思想。 题意 有\(n\)个城市分布在小鸟岛上，有\(m\)个弹弓分布在这些城市里。因为弹弓体积大，固定麻烦，所以每个弹弓只能把小鸟弹飞到一块固定的矩形范围内的城市，同时小鸟会在空中滞留\(t_i\)的时间。闪电黄的家在1号城市，追求速度的它想知道，若只使用弹弓出行，它从家到其他所有城市的最短时间花费是多少。 抱歉魔...

P5658 括号树 NOIp2019 我是永远不会忘记我那天在考场上傻瞪着题啥都不会的心理阴影的…… 于是今天我克服心理阴影来写这道题。 树形结构 因为这是一个树，所有优秀的性质这个题都有。并且题目仅仅是问从1开始到所有点的答案，所以我们就可以依靠树的性质来做。 首先，对于一个节点，我们给它记录几个值： \(lst_i\)表示i的贡献（只是i的贡献，并不包括从根节点到i路径...

P6106 [Ynoi2010] Self Adjusting Top Tree 题意 给出平面直角坐标系上若干不与坐标轴平行的处于第一象限的互不相交的线段，多次询问平面中一个第一象限的矩形与这些线段相交部分的长度长度和与所有线段长度和的比值。给出的所有坐标 \(\in[1,10^6]\)。 思路 假设所有线段的斜率都是正的，考虑将询问差分成四个前缀矩形。我们只需要考虑统计若干斜...

P6295 有标号 DAG 计数 题意 求 \(n\) 个点有标号弱联通 DAG 数量。 推导 设 \(f_i\) 表示 \(i\) 个点有标号 DAG 数量（不保证弱联通），有： \[ f(i)=\sum_{j=1}^i\binom ij(-1)^{j-1}f(i-j)2^{j(i-j)} \] 意义为选至少 \(j\) 个度数为零的点，向剩下的 \(i-j\) 个点随...

P6753 [BalticOI 2013 Day1] Ball Machine 题意 给你一个树，每次从根节点放一个求，如果其子节点有空这个球会向下滚，若有多个节点为空则找儿子中以子树内编号的最小值为优先级从小到大找第一个为空的位置滚。 有两种操作，第一种插入若干个球，输出最后一个球到的节点编号；第二种删除一个位置，此时若有可以向下滚的球那么这个球就会滚，输出有多少个球滚了。 保证...

P6845 [CEOI2019] Dynamic Diameter 题意 一颗带权树，每次更改一条边的权，每次修改后求出最大直径。强制在线。 思路 \(O(n\log^2n)\) 的暴力做法。 根据经典结论，对于两个点集的树上最大直径（权值非负），并集点集的树上最大直径的端点一定是原四个端点中的两个。 那么我们就可以用线段树维护点集，合并时 \(O(\log n)\) 查询两点...