D1T2：

解题思路：

感觉没啥好说的，难点在点分树、每对相邻点的最优距离绝对值不超过 \(1\) 和函数是凸的上。 但我随便猜猜也就猜出来是凸的了，然后调整一下就有相邻的决策点距离不超过 \(1\)，所以难点还是点分树（）

D2T1：

题目大意：

给定一个长度为 \(n\) 的序列 \(a\)，你要将他划分成恰好 \(k\) 段，使得每段的中位数的中位数最大。 \(n \le 10^6\)。

解题思路：

首先二分答案是显然的，那么一个段最终的和 \(\ge 0\) 时中位数就会 \(\ge mid\)，而我们只需要保证这 \(k\) 段中至少有 \(\lceil \frac{k}{2} \rceil\) 段 \(\ge 0\) 的即可。

考虑一种划分方案，显然地可以暴力 \(dp\)。

发现直接考虑划分方案的话 \(dp\) 要存的状态太多了，不是很好优化。

发现有一个大小为 \(n\) 的状态全都用来丢给恰好 \(k\) 段这个限制上，考虑能不能通过调整段数来做到恰好为 \(k\) （在满足这些段中至少有 \(\lceil \frac{k}{2} \rceil\) 段 \(\ge 0\) 的前提下）。

如果当前段数小于 \(k\)，首先可以将所有没有贡献的段都拆开，然后如果还是不够的话继续拆有贡献的段，这样会使 \(\ge 0\) 的段数不减的情况下增加到 \(k\)。

如果当前段数大于 \(k\)，考虑能不能进行合并操作，也就是两段 \(\ge 0\) 的段中间不会有超过一个不贡献的段，那么设 \(cnt\) 表示有多少 \(\ge 0\) 的段相邻，此时 \(< 0\) 的段数即为 \(\lceil \frac{k}{2} \rceil + 1 - cnt\)，但这时候不还是要保证 \(2x+1-cnt \le k\) 吗，但通过合并 \(01\) 段，就能将 \(x\) 降到恰好 \(\lceil \frac{k}{2} \rceil\)，但构造是通过不变 \(cnt\) 的条件下。

你会发现此时 \(cnt\) 只关心他是否 \(\ge O(1)\) 即可，所以还是能 \(dp\)，但是要特判 \(k \le 5\)。

主要是刻画明白题目，打个 5h 比赛的 t1 我急啥/yiw

D2T2：

题目大意：

给定一个长度为 \(n\) 的数组 \(a\)，每次询问给定一个 \(l \sim r\)，将 \(b\) 数组设为 \(a_{l} \sim a_{r}\) 之后每个数与 \(r - l + 3\) 取 \(min\)，这样就变成了一个 \(prufer\) 序列，然后给定 \(1 \le x,y \le r - l + 3\)，判定 \(x,y\) 是否相邻。 \(n,q \le 2 \times 10^5\)

解题思路：

考虑 \(prufer\) 的建造过程，首先会将所有没出现过的数加入堆中，然后每次将堆中最小值和 \(a_{i}\) 连边，如果 \(a_{i}\) 后面没有 \(a_{i}\)，那么把 \(a_{i}\) 也加入到堆中。

考虑我们只关心 \(x,y\) 分别在什么时候被弹出队列，所以只关心堆中 \(\le x\) 的个数（\(y\) 同理），在加入 \(x\) 之后第一个 \(\le x\) 个数为 \(0\) 的位置就是我们要求的位置。

这样一来，注意到我们只关心每个点最后出现的位置，且他会在 \(p+1\) 这个位置加入队列。

而且注意到每个位置无论是否加如，队列中总是会 \(pop\) 一个数，而每个位置又最多加入一个点，所以可以在扫描线的过程中二分 \(check\)，假设最终的位置是 \(p > lst_{x}\)。

而这个东西可以拿树套树维护，前面一维是值域（BIT），后面一维是下标（线段树），这样 \(O((n+m) \log^3 n)\)，套路地，将二分放到线段树中，\(O(n \log^2 n)\)。