P3203 弹飞绵羊-分块 观察数据范围，发现可以分块。只需要处理每个点跳出所在块后的位置和次数即可。目的是为了加速查询并降低修改复杂度。 对于修改，重构整个块内信息即可。 时间复杂度正确的一批 具体实现也挺简单。注意重构时从后往前贡献即可。 1234567891011121314151617181920212223242526272829303132333435363738394...

P2491 消防/P1099 树网的核 双倍经验，双倍快乐。 题意 在一个树上选择一段总长度不超过\(s\)的链使所有点到该链距离的最大值最小。 输出这个最小的值。 做法 Define:以下\(s\)指链或链长。 证明一下\(s\)一定处于直径上。假设它不在直径上，一定存在直径的其中一个端点到\(s\)的距离大于现在所处支链的最大距离。所以\(s\)不在直径上一定不优。 ...

平面图 平面图就是所有点的连边可以在平面上不相交的图。这一点可以大概理解成拓扑图的性质，即每连一条边就会将某个区域进行分割——很明显，如果两个点分别处在两个不可达的区域，它们要连边显然是要穿过其他边的。 平面图定理 边数大于点数的三倍减六的图一定不是平面图。即设n为点数，m为边数，有 \[m<=n*3-6\] 关于平面图的其他定理和上定理的证明我不会不过我有大佬博客就不乱搬了...

P3214 [HNOI2011]卡农 题意 在集合 \(\{1,2,\cdots,n\}\) 中选出 \(m\) 个非空子集满足： 不存在完全相同的两个集合； 每个元素在所有集合中出现次数之和为偶数。 思路 考虑转移，利用容斥方法进行 Dp。设 \(f_i\) 表示选了 \(i\) 个集合满足条件的方案数： 首先，如果确定了前 \(i-1\) 个集合，那么为了满...

P3643 [APIO2016]划艇 题意 一个合法序列可表示为一个长度为 \(n\) 的序列，其中第 \(i\) 个数可以为 0 或 \([l_i,r_i]\) 中一个整数，且满足所有不为零的数组成的子序列严格上升。求合法序列方案数。\(n\leq 500,l_i\leq r_i\leq 10^9\)。 思路 朴素动态规划做法为，设 \(f_{ij}\) 表示第 \(i\)...

P4074 [WC2013]糖果公园 树上带修莫队 题意：树上每个点有一种糖果，求\(\sum_c\sum_{i=1}^{cnt_c}v_c*w_i\) 其中c为糖果种类，\(cnt_c\)其为出现次数。 思路 离线树上带修莫队。 先进行树上分块。分块内的询问按照出发点、终止点、询问id优先级依次递减排序。 对于树上莫队，其实就是在欧拉序上莫队。因为欧拉序的性质，即每个节点子树...

P3312 数表 题意 求出 \[ \sum_{i=1}^n\sum_{j=1}^m\sigma(\gcd(i,j))[\sigma(\gcd(i,j))\le a] \] 其中 \(\sigma\) 表示约数和。 思路/推导 考虑没有 \(a\) 的限制的情况。 \[ \begin{aligned} ans&=\sum_{d=1}^{\min(n,m)}\sigm...

P4168 蒲公英 暴力分块思想。分块的思想与莫队相同。它能将时间和空间复杂度均摊XD belong 表示所属区块，num 维护区间颜色出现次数，maxx 维护区间 max 值。查询时只需要比较两端的区块即可。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474...

P4169-CDQ分治/K-D tree（三维偏序）-天使玩偶 这是一篇两种做法都有的题解 题外话 我写吐了…… 本着不看题解的原则，没写（不会）K-D tree，就写了个cdq分治的做法。下面是我的写题步骤： 想着树状数组维护不了区间最值，于是写了线段树，因为一个**的错误调了几个小时； cdq只写了两个方向。显然是错的，因为没考虑修改。所以挂了； 加上另外两个方向，...

P4180 [BJWC2010]严格次小生成树 题意 求出一个无向联通图的严格次小生成树。严格次小生成树的定义为边权和大于最小生成树的边权和但不存在另一棵生成树的边权和在最小生成树和严格次小生成树之间（不相等）。 思路 先求出一颗最小生成树，发现严格次小生成树一定是其断了一条边并加了一条边且边权和的增加量最小。 那么我们继续在最小生成树上做。对于每一条不是最小生成树上的边，求出其两...