ARC067D Yakiniku Restaurants

题意 : 在一条街道上有 家烧烤店，由近至远编号为 。第 家与第 家店的距离为 。

初始时，你手上有编号为 的烧烤卷各一张。

第 家店使用编号为 的烧烤卷可以获得的收益为 ，每张卷只能用一次。

你可以任选一家店作为起点出发，用完所有 张卷。

求 吃烧烤的收益减去行走的路程 的最大值。

，，时限 。

---

显然，能到访的店是一个区间，则从区间的某一端开始，总路程最短。

令第 家烧烤店的坐标为 ，用 计算出每家烧烤店的坐标。

使用序列扫描线。逐渐增大右端点 ，并维护每个左端点 的贡献。

记 表示在区间 内使用卷 所能获得的最大收益。

那么在区间 所能获得的最大收益即为 。

考虑如何维护 。

对于每张卷，使用单调栈维护 ，可以将修改转化为 次区间加法。

将区间加法转化为差分，可以 维护 各个 的差分数组。当然也可以得到 的差分数组。

对于每个 ，枚举 并计算答案即可。利用差分计算各个 。

复杂度为 。