题意

数轴 $[0,m]$ 上有一只老鼠，初始时可能位于数轴上的任意点。这只老鼠可以在数轴上任意移动，但是任何时刻瞬时速度不超过 $1$ 个单位每秒。

有 $n$ 只机器猫，部署第 $i$ 只的代价为 $w_i$，部署后它会在 $t_i$ 时刻出现在 $a_i$，以每秒 $1$ 个单位的速度向 $b_i$ 移动。

老鼠初始时有 $k$ 点血量，如果在某个时刻和一只机器猫完全重合，就会减 $1$ 点血量，这只机器猫也会被销毁。

求最小代价，使得无论老鼠如何移动，最终血量都 $\leq 0$。多测，$\sum n\leq 3\times 10^5$，$k\leq 10$。

题解

场外选手。激战一百年，也是自己做出来了，有点开心。

考察老鼠的移动有什么限制，移速不超过 $1$，意味着对于一个时间段都有 $|\Delta x|\leq \Delta t\Leftrightarrow -\Delta t\leq \Delta x\leq \Delta t$，也就是说，$\Delta t+\Delta x\geq 0\land \Delta t-\Delta x\geq 0$。考虑变换坐标，令 $(t,x)\gets (t-x,t+x)$，这样老鼠的初始位置为 $(-p,p)$，且任意时刻都要满足 $\Delta x,\Delta y\geq 0$，相当于只能朝着右上方移动。考察 $0\leq x\leq m$ 的限制，代入 $x=\dfrac{(t+x)-(t-x)}{2}$，可以得出 $t-x\leq t+x\land t-x\geq t+x-2m$，也就是说，老鼠还被限制在 $y=x$ 和 $y=x+2m$ 两条直线之间。

考虑变换坐标后，机器猫的移动路径。若 $a_i\leq b_i$，则

$$\begin{align*} x=a_i+t-t_i&\Leftrightarrow t-x=t_i-a_i\\ t\in [t_i,t_i+(b_i-a_i)]\land x\in [a_i,b_i]&\Leftrightarrow t+x\in [t_i+a_i,t_i+(b_i-a_i)+b_i] \end{align*}$$

此时机器猫的移动路径为一条垂直线段。

同理，若 $a_i>b_i$，可以得到 $t+x=t_i+a_i\land t-x\in [t_i-a_i,t_i+(a_i-b_i)-b_i]$，机器猫的移动路径为一条水平线段。

现在问题就转化成了：有一个点 $(-p,p)$，只能朝着右上方移动，被限制在 $y=x$ 和 $y=x+2m$ 两条直线之间。现在有一些垂直或水平的线段，要求以最小代价选取一些线段，使得无论点如何移动，都会碰到至少 $k$ 条线段。

不妨先做 $k=1$，相当于要选出若干条线段使得老鼠无法通过。考察一组合法线段的形态：

黑色实线是我们选出来的线段。可以发现，选出来的线段一定能围出一个分界线（图中绿色虚线），使得一边是老鼠可达的区域，另一边是老鼠不可达的区域。不妨给分界线定向，以与 $y=x$ 的交点为起点，与 $y=x+2m$ 的交点为终点。可以发现这样定向之后，沿着分界线走，向左或向上走时一定是沿着线段走的，向右或向下走时则不是（这是老鼠只能往右上走的限制自然形成的分界线）。不妨考察相邻线段之间的限制，钦定一条线段的起点为靠近 $y=x$ 的那一端，终点为另一端，设 $u$ 为第 $i$ 条线段的终点，$v$ 为第 $i+1$ 条线段的起点，则可以分讨得出，$u$ 和 $v$ 之间的限制为 $u_x\leq v_x\land u_y\geq v_y$。

据此考虑图论建模，套路地将线段 $i$ 拆成 $in_i,out_i$ 两个点，从 $in_i$ 向 $out_i$ 连一条权值为 $w_i$ 的边。对于任意两条线段 $i,j$，若 $i$ 的终点 $u$ 和 $j$ 的起点 $v$ 满足前文中的性质，则从 $out_i$ 向 $in_j$ 连一条权值为 $0$ 的边。最后建立源点 $S$ 和汇点 $T$，对于每条线段 $i$，若 $i$ 的起点在 $y=x$ 上，则从 $S$ 向 $in_i$ 连一条权值为 $0$ 的边；若 $i$ 的终点在 $y=x+2m$ 上，则从 $out_i$ 向 $T$ 连一条权值为 $0$ 的边。这样建图后，不难看出答案就是 $S$ 到 $T$ 的最短路。

考虑进一步推广到 $k>1$ 的情况，此时我们需要选出 $k$ 条不交的分界线。不难想到网络流，将连边改为：

• $in_i$ 向 $out_i$ 连一条容量为 $1$，权值为 $w_i$ 的边。
• 从 $out_i$ 向 $in_j$ 连一条容量为 $+\infty$，权值为 $0$ 的边。
• 从 $S$ 向 $in_i$ 连一条容量为 $1$，权值为 $0$ 的边。
• 从 $out_i$ 向 $T$ 连一条容量为 $1$，权值为 $0$ 的边。

此时从 $S$ 到 $T$ 的 $1$ 个单位的流量就代表选出了一条分界线，那么我们限制最大流 $\leq k$，求最小费用最大流即可。具体来说，每一轮增广的流量为 $1$，那么我们增广 $k$ 轮即可，最终费用就是答案，若无法增广 $k$ 轮则无解。

建出来的图边数是 $\mathcal{O}(n^2)$ 的，时间复杂度为 $\mathcal{O}(kn^3)$，可以获得 $56$ 分。

进一步优化，注意到连边条件为二维偏序的形式，因此考虑 CDQ 分治优化建图。具体来说，考虑 $n$ 条线段的 $2n$ 个端点，将所有端点按 $x$ 坐标从小到大排序，$x$ 坐标相同的按 $y$ 坐标从大到小排，$y$ 坐标相同的把线段终点排在起点前面（读者需要理解一下这个排序方式，其实是为了处理取等）。CDQ 分治，递归到 $[l,r]$ 时处理所有跨过 $mid$ 的连边：分别取出左侧的线段终点和右侧的线段起点，按 $y$ 坐标排序，枚举左侧的线段终点 $u$，则其能连向的线段起点 $v$ 是一段前缀，使用前缀优化建图即可。这样点数和边数都是 $\mathcal{O}(n\log{n})$ 级别的，时间复杂度为 $\mathcal{O}(kn^2\log^2{n})$，可以获得 $84$ 分。

改成用原始对偶求费用流，由于边权非负，初始时不必跑 SPFA，将势能初始化为 $0$ 即可，时间复杂度为 $\mathcal{O}(kn\log^2{n})$，可以获得 $100$ 分。