AGC011F Train Service Planning

题意：有一条铁路，被 个站台分为 段。站台标号为 ，铁路标号为 。

列车通过第 段所需时间为 ，可能是双向的或单向的。

现在需要设计一张列车（循环）时刻表。

对于所有的列车，要么从站台 前往站台 ，要么从站台 前往站台 。

在单向轨道内，不能有两辆相反方向的车互相穿过。列车只能在站点停车等待。

若有一辆开往 的车在时刻 到达站点 ，在时刻 离开站点 ，则下一辆车恰好在时刻 到达站点 ，在时刻 离开站点 。其中 是给定常数。

需要使得时间表中 与 的列车的所需时间和最短。回答这个最小值，或指出无解。

，时限 。

---

应用题啊……

当某个 则无解，否则必定有解。

记 表示 的车在站点 停靠等待的时间。

表示 的车在站点 停靠等待的时间。记

某个方向的车经过第 段铁路的时间为一段区间，且每 单位时间重复一次。

具体地，在模 循环意义下：

上行车的区间为

下行车的区间为

实际上下行车的式子是全体减去前缀得到后缀，但是走一整次所需的时间是 的倍数，所以在模 意义下可以忽略。这样形式上会更统一。

若这是单向铁路，要求两个区间（在模 意义下）不交。

记 ，上式可以统一为 ：

对 的唯一约束是：单调不减。

• 于是问题可以转化为：

  你有一个变量 ，初始值任意。

  每次会给出一个模 意义下的区间，要求给 加一定值，使得 落在这个区间内。

  最小化加上的值的和。

  （在本题中，还需加上 才是答案）

---

考虑 。记 为第 次操作后使得 所需的最小代价。

显然我们需要关心的 一定为给出的某个端点。

边界：。

每次操作时，设给出的模意义区间为 ，让 以外的位置转移到 上，然后将它们置为 ，其余不变。

维护 的区间 即可。

复杂度 。