[CF2042D] Recommendations
发现所求即为包含 \([l,r]\) 的所有区间的交的长度减去 \([l,r]\) 的长度。考虑所有包含 \([l,r]\) 的区间 \([L,R]\)，不难发现其满足 \(L\le l,r\le R\)。由于我们要求交，所以求出满足该条件的 \(L\) 的最大值和 \(R\) 的最小值即可。扫描线处理即可。
[HDU5603] the soldier of love
我们要求出至少包含一个点的区间个数，不难想到容斥转化为求一个点都不包含的区间个数。那么如果给定的点事 \(P_1,P_2,P_3,\cdots,P_k\) 的话，这样的区间就只能在 \([1,P_1),(P_1,P_2),(P_2,P_3),\cdots(P_k,N]\) 之中，也就是区间的 \([l,r]\) 要同时属于上面的某一个区间。发现这样的区间构成了 \(k+1\) 个矩形，所以离线扫描线处理即可。
[UOJ637] 数据结构
我们要求区间出现的数的个数，由于值域只有 \(n\)，考虑求出哪些数出现了。这个问题可进一步转化为求那些数字没有出现，那么修改完一个区间 \([l,r]\) 后，\(x\) 没有出现需要满足以下两个条件：
- \([l,r]\) 包含所有的 \(x\)。
- \([l,r]\) 不包含任何一个 \(x-1\)。
假设 \(x\) 第一次出现在 \(L\)，最后一次出现在 \(R\)，第一个条件等价于 \(l\le L,R\le r\)。而第二个条件仿照上一题即可处理。两个限制都是矩形的形式，求交之后就是 \(x\) 的贡献，然后扫描线处理即可。
[PKUSC 2024] 排队
我们考虑扫描线，对于每一个询问左端点 \(L_i\) 我们往当前集合里插入一个 \(0\)，表示这个询问当前的函数值。然后我们计算一下在当前位置上进行函数操作之后所有值的变化。不难发现，只有集合中在 \([l_i,r_i]\) 之间的数才会被加上 \(1\)，别的不会变。
我们考虑用平衡树维护这个集合，然后按值分裂即可得出在 \([l_i,r_i]\) 之间的数，给根节点打上一个全局加 \(1\) 标记再合并即可。由于单次只会加一，所以不会出现值域重复的情况。
当我们扫到一个 \(R_i\) 的时候，找到原先在 \(L_i\) 处插入这个询问的函数值时对应的节点，此时该节点上的值应该就是答案。但是此时它的祖先可能还有一些标记没有下放，我们记录下父亲然后暴力跳父亲累加标记即可。
复杂度 \(O(n\log n)\)，但是常数过于巨大。
[CF1172F] Nauuo and Bug
考虑到题目中所给的 \(\text{AddMod}\) 操作本质上还是一个分段函数，所以考虑利用函数复合的套路处理。我们考虑扫描线，每一次加入一个 \(0\)，然后对于当前位置上的函数操作，先对全局加 \(a_i\)，然后再将 \(\ge p\) 的部分减去 \(p\) 即可。
不难发现上述过程可用平衡树简单维护，但是此时分裂出 \(\ge p\) 的部分再减去 \(p\) 之后至于会有重复，这个时候我们可以使用一种合并值域有交的平衡树合并方式，也就是考虑将值域划分成几段，按照大小依次拼接。根据均摊分析，这样做的复杂度是 \(O(n\log^ 2 n)\) 的。
最后我们记录下插入时点对应平衡树上的节点，然后暴力跳父亲累加标记即可。复杂度 \(O(n\log^2 n)\)。
[SDOI2014] 里面还是外面
考虑一个计算几何的经典结论：从一个点向外发出一条射线，如果这条射线经过了奇数条边，则它在这个简单多边形内部，否则在外部。在边界上的情况需要特判。
我们考虑利用这个结论，把这条射线的方向固定为竖直向上，则我们只需要找出比当前点的 \(y\) 坐标大的所有线段即可。由于这是一个简单多边形，所以不会有线段相交，所以比当前点高的线段可以构成偏序关系（也就是可以按纵坐标排序）。
我们考虑对 \(x\) 轴建立线段树，每一个区间 \([l,r]\) 内维护左端点 \(\le l\)，右端点 \(>r\) 的所有线段构成的集合。然后在内层用平衡树来维护这个集合。不难发现这是区间修改、单点查询的树套树，所以每一次查询的时候要走一遍儿子到根的路径，在平衡树上二分出满足要求的线段数量并累加，最后判断数量是奇数还是偶数即可。
由于区间是左闭右开，所以多边形中的端点可能会漏判，遇到这种情况可以直接存下所有的端点然后特判即可。复杂度 \(O(n\log^2 n)\)。
[CEOI2024] 加油站
考虑维护树上路径使用点分治，然后套路的容斥排除子树内对子树内的贡献，则我们对于一个子树只需要考虑所有子树的贡献即可。接下来考虑经过重心 \(u\) 的路径的贡献，我们分成两部分考虑，即 \(a\to u\) 的部分和 \(u\to b\) 的部分。
对于第一个部分的贡献，我们可以倍增求出在当前节点加满油后，能走到的深度最小的节点，那么我们就必须这个走到的节点加油。也就是说，所有需要在当前点加油的车都必须在走到的那个节点加油，累加贡献计算即可。注意累加到答案上时还要乘上其他子树的大小。如果可以直接走到根，那么就将剩余油量求出来。
然后考虑第二个部分的贡献，我们发现这一部分较为难维护，因为你在不在一个点加油是取决于它走到哪个儿子的。所以我们考虑转化一下，把贡献记到儿子身上。也就是说，如果一辆车在走到 \(x\) 之后，下一步走到 \(y\) 需要加油，我们把 \(x\) 的贡献存到 \(y\) 里。这样，我们会发现此时的要求就是到 \(y\) 的距离 \(>k\) 而到 \(x\) 的距离 \(\le k\)。
如此，我们就可以发现对单个点 \(y\) 做出贡献的点其祖先中的一段区间，可以直接二分求出。然后我们就要求出这一段的贡献总和，所以做的时候还要进行一次树上前缀和。当然不要忘了上面我们记录了跳到根的一些剩余油量，我们同样在这个序列上二分就可以求出对应贡献了。
排除贡献的方式和上面是一样的，总复杂度 \(O(n\log^2 n)\)。
[WC2018] 通道
对于树上路径考虑点分治，我们对第一棵树进行一次点分治，统计经过当前分治中心的路径贡献。不难发现，此时对于在两个子树内的点 \(u,v\)，其在第一棵树上的贡献就是 \(dis1_u+dis1_v\)。然后考虑第二棵树的求解，此时我们的目标是让 \(dis1_u+dis1_v+dis2(u,v)+dis3(u,v)\) 最大，考虑将 \(dis2(u,v)\) 拆开，得到 \(dis1_u+dis1_v+dis2_u+di2_v-2dis_{\text{lca}(u,v)}+dis3(u,v)\)。
不妨在第二棵树上枚举 \(\text{lca}(u,v)\)，则剩余部分的值即为 \((dis1_u+dis2_u)+(dis1_v+dis2_v)+dis3(u,v)\)。如果我们在第三棵树上给每个点 \(u\) 连一个虚点 \(u'\)，边权为 \(dis1_{u}+dis2_u\)，则这个式子实际上相当于在第三棵树上求直径（当然要保证直径两端点在第一棵树上属于不同的子树）。由于边权全部为正，所以直径可以直接合并，于是只要枚举 \(\text{lca}(u,v)\) 之后就可以直接合并子树求出直径。
当然直接枚举的复杂度会炸，我们当前在第一棵树上只求解两个子树间的贡献，所以把这些点建出虚树即可。最后由于我们在第一棵树上单次只能处理两个子树，所以要考虑一下合并顺序。我们采用哈夫曼树合并的思路，每次将两个最小的树合并起来，可以证明，这样的复杂度仍然是 \(O(n\log n)\)。
总复杂度即为 \(O(n\log^2 n)\)，如果强行优化掉虚树的 \(\log n\) 排序和求 \(\text{lca}\) 的 \(\log\) 的话也可以做到 \(O(n\log n)\)。
事实上由于我们单次只能合并两个子树，所以边分治是更适用于此题的。
[IOI2020] 连接擎天树
我们先来考虑前 \(96\) 分的部分分，即 \(0\le p_{i,j}\le 2\)。
首先可以想到根据 \(0\) 将整张图划分为几个连通块，此时就只用考虑 \(1\le p_{i,j}\le 2\) 的情况了。发现如果一张图中有两个环一定不合法，因为此时两个环上的两个点之间的路径数是 \(4\)。所以整张图一定是基环树或者树。
对于这两种情况，我们将所有 \(p_{i,j}\) 为 \(1\) 的合并到一个连通块中，然后随便连边。接下来从这些连通块中每个选一个点连成环即可。如果只有两个连通块则无法连出环，判掉无解即可。
需要注意的是上面每一次划分连通块要保证每一个连通块中的每一对点都满足对应要求。不然的话要判无解。
然后考虑 \(p_{i,j}=3\) 的情况，发现此时图上也一定构成了两个环，所以判掉无解即可。复杂度 \(O(n^2)\)。
[LOJ6669] Nauuo and Binary Tree
考虑先用 \(n-1\) 次询问询问出所有点的深度，然后按照深度来一个个查询。假设我们已经处理前面一部分点，现在处理第 \(i\) 个点，我们考虑对已经处理出来的部分做一次树链剖分，然后从根节点开始做如下操作：
- 利用深度求出以当前点作为链头的链长度，以及 \(i\) 到链头的距离。询问一次 \(i\) 到链底的距离。
- 通过上面三个信息可以判断出 \(i\) 在链上哪个点的子树内，由于树是二叉树，所以每个节点不是重儿子就是轻儿子，而 \(i\) 必然在链上那个点的轻儿子内。接下来进行判断，如果该节点没有轻儿子，直接连边并退出；否则我们递归到该儿子的轻儿子中，重复上述操作即可。
由于重链剖分的性质，不难发现这样询问一个点的次数是 \(O(\log n)\) 的，总次数 \(O(n\log n)\)，由于树链剖分常数小，该复杂度可以通过。
[CERC2014] Parades
考虑 dp，设 \(dp(i)\) 表示在 \(i\) 子树内放链的最大值，考虑转移。我们将所有 \(\text{lca}\) 在 \(i\) 处的链放到 \(i\) 来考虑，这个时候如果放下这些链，可能会对子树中的答案造成影响。但是发现如果造成影响，子树内答案会减少至少 \(1\)，而答案至多增加 \(1\)，所以一定不会更优。
于是我们要先保证 \(i\) 的所有儿子 \(j\) 能取到 \(dp(j)\)，然后再考虑放置这些链。所以额外维护 \(f(x,i)\) 表示在 \(dp(x)\) 取到最大值的时候 \(x\to i\) 这条链上是否可以没有游行队伍。在判断这些链的时候，我们先判断一段在 \(i\) 上的链，此时我们只需要看另一端的 \(f\) 值是否为 \(1\) 即可。
然后考虑跨两个子树的链，首先要保证路径上可以没有游行队伍，然后还要保证选出来的链两两不交。可以将每一个儿子看成一个节点，这些链相当于连边，则此时我们要求的就是一个一般图最大匹配，这里由于一个点最多 \(10\) 个儿子，所以可以直接 \(O(\text{deg}2^{\text{deg}})\) 状压 dp 来实现。
总复杂度 \(O(n^2+n\times \text{deg}\times 2^{\text{deg}})\)，可以通过。
[六省联考 2017] 摧毁“树状图”
大力树形 dp + 分类讨论即可。设以下状态：
- \(f(x,0)\) 表示只选择从 \(x\) 为起点到子树中的一条链删去后的答案（下直接简写为“答案”）。
- \(f(x,1)\) 表示选一条经过 \(x\) 的链的答案。
- \(f(x,2)\) 表示选一条不经过 \(x\) 的链的答案。
- \(f(x,3)\) 表示选一条以 \(x\) 为起点到子树中的一条链和另一条链的答案。
然后考虑转移，继续分讨：
- \(f(x,0)\) 显然只能从一个儿子继承过来。
- \(f(x,1)\) 可以从儿子继承，也可以选两条链拼起来。
- \(f(x,2)\) 只能从儿子继承。
- \(f(x,3)\) 是最复杂的，我们需要考虑另一条链的位置。分为经过 \(x\)，经过 \(x\) 的儿子和不经过 \(x\) 的儿子来计算。然后还可以继承儿子的状态。
需要注意的是转移的时候注意当前节点和儿子的状态，有的时候并不对称，因此需要写两个方程。最后是求答案：
- 用一个 \(f(x,3)\) 和一个 \(f(y,0)\) 拼起来。
- 用在两棵子树中的两条链拼起来，也就是 \(f(x,1)/f(x,2)\) 和 \(f(y,0)/f(y,1)\) 拼起来。
最后还需要注意有人不走或者经过根节点的链也是一条根链的情况。前者我们可以将答案和 \(f(x,0/1/2/3)\) 都取一遍 \(\max\)，后者可以把 \(f(x,1)\) 对 \(f(x,0)\) 取 \(\max\)。
[NOI2014] 购票
首先这是一个显然的 dp 题，我们可以列出如下转移式：
\[dp_u=\min_{dis_u-dis_v\le l_u}\{dp_v+(dis_u-dis_v)\times p_u+q_u\} \]不难发现这是一个标准的斜率优化式子，但是此时我们有了 \(dis_u-dis_v\le l_u\) 的限制，移项得 \(dis_v\ge dis_u-l_u\)。假如我们是在序列上做这个操作，那么这个可以看作是一个二维偏序，用 CDQ 分治加斜率优化即可。
现在我们在树上做这个问题，同样的考虑分治，那么自然能想到利用点分治来进行求解。由于此题给出的是有根树，所以分治过程不太一样。
- 我们先找出子树的重心，然后递归处理重心上方的那颗子树。
- 利用上方子树的信息去更新下方的子树。由于上方的子树自然满足 \(dis\) 单调递减，所以无需排序，只需要对下方子树的节点按照 \(dis_u-l_u\) 从大到小排序即可。
- 递归处理下方的子树。
最后加上斜率优化 dp 即可，注意到由于本题的斜率 \(k=p_u\) 不满足单调性，所以需要凸包上二分 / 李超线段树来求解。复杂度 \(O(n\log^2 n)\)。
[2021 集训队互测] 蜘蛛爬树
发现我们一定是走到一个点，然后沿着蛛丝一直走下去，最后再走到终点最优。这个是显然的，因为如果你在中间换点走更优，那肯定不如最开始就走这个点了。
所以我们会得到答案就是 \(\min\{dis(u,i)+dis(i,v)+ka_i \}\)，其中 \(k\) 是两棵树之间的距离。我们进一步将其拆分为 \(dis_u+dis_i-2dis_{\text{lca}(u,i)}+dis_v+dis_i-2dis_{\text{lca}(v,i)}+ka_i\)。我们知道，\(\text{lca}(u,i),\text{lca}(v,i),\text{lca}(u,v)\) 中至少有两个相等，而不管哪种情况，我们都只需要枚举一个 \(\text{lca}\)。所以做如下分类讨论：
- \(\text{lca}(u,i)=\text{lca}(u,v)\) 时：
我们只需要枚举 \(\text{lca}(v,i)\)，此时它一定在 \(v\to \text{lca}(u,v)\) 的路径上，并且价值是 \(dis_u+dis_v-2dis_{\text{lca}(u,v)}+2dis_i-2dis_{lca}(v,i)+ka_i\)。我们发现前面的东西就是 \(dis(u,v)\)，所以维护后面的东西即可。发现这是一个一次函数的形式，应该可以用李超线段树 / 凸包维护之。
\(\text{lca}(v,i)=\text{lca}(u,v)\) 同理，不再赘述。
- \(\text{lca}(u,i)=\text{lca}(v,i)\) 时：
我们枚举 \(\text{lca}(u,i)\)，此时它一定在 \(\text{lca}(u,v)\) 的祖先上，并且价值为 \(dis_u+dis_v+2dis_i-4dis_{lca}(u,i)+ka_i\)。显然这也是一次函数的形式。
但是我们会发现一个问题，一方面我们如果存储所有的一次函数就要遍历每一个点的子树，复杂度是 \(O(n^2)\) 的；另一方面我们要查询的是树上一段区间中每一个点上的一次函数最值，所以理论上需要树套树加树剖，复杂度会来到 \(O(n\log^3 n)\)，也无法通过。
我们依然考虑树剖，但是这个时候对于每一个点我们不考虑它和所有子孙构成的一次函数，只考虑轻儿子子树内的子孙和自己即可，这样的话函数的数量就可以降到 \(O(n\log n)\)。然后我们依然利用线段树来维护，不过内层我们换成凸包，先在开始的时候将询问按照 \(k\) 排序，这样查询的最值在凸包上是单调不减的，可以维护一个指针来做，复杂度降至 \(O(n\log^2 n)\)。
但是这么做还有最后一个漏洞，我们在链头的父亲处以及两个端点处无法正确统计答案。发现这个时候每一个儿子的贡献依然是一次函数，所以重新建一颗线段树来维护它所有儿子的函数构成的凸包，在上面直接查询即可。
所以最后的总复杂度就是 \(O(n\log^2 n)\)，可以通过此题。
[JOISC 2019 Day1] 聚会
我们继续利用树上三个点的优秀性质。我们设一个函数 \(\text{solve}(x,S)\) 表示当前确定了 \(x\) 的子树里有 \(S\) 这些点的求解。我们随机从 \(S\) 中取一个 \(y\)，然后剩下的点一个个问 \(\text{Query}(x,y,p)\)。如果返回的是 \(p\) 说明 \(p\) 在 \(x-y\) 这条链上，否则 \(p\) 就在返回的点的子树中。
接下来对于链上的点我们直接询问 \(\text{Query}(x,a,b)\) 就可以知道谁离 \(x\) 更近，以此作为快排标准排序，然后就可以得出这条链上的连边情况。然后递归处理链上的每一个节点和它的子树即可。
由于保证了岛屿的度数不超过 \(18\)，所以这个随机化的算法正确率很高，可以通过。
标签：2024.12,log,记录,text,即可,lca,我们,dis From： https://www.cnblogs.com/UKE-Automation/p/18662293