决策单调性优化DP

· · 算法·理论

基础知识

四边形不等式

如果一个二元函数 w 满足对于所有 a\le b\le c\le d，满足

w(a,c)+w(b,d)\le w(a,d)+w(b,c)

那么称其满足四边形不等式。因为在求 \max 和求 \min 的不同情况下，四边形不等式的方向不同，所以为了方便，我们记它为 \min 四边形不等式。于是满足

w(a,c)+w(b,d)\ge w(a,d)+w(b,c)

的简便地记为 \max 四边形不等式。

下面讨论的四边形不等式均为 \max 四边形不等式，\min 的各种性质和 \max 的证明方式无大的区别。

四边形不等式还有一个等价形式：对于任意 j<i，满足

w(j,i)-w(j-1,i)\ge w(j,i-1)-w(j-1,i-1)

一般证明四边形不等式就利用这种形式或类似这种的形式，这样只需要考虑从 i 和 i-1 分别从 j 处扩展到 j-1 处的贡献。

动态规划中我们经常列出 f_j+w(j,i) 这种式子。当 w(j,i) 满足四边形不等式时，w'(j,i)=f_j+w(j,i) 也是满足四边形不等式的，因为式子中 f_j 和 f_{j-1} 都被恰好消掉了。

这个式子其实不用怎么特别记为『交叉小于包含』或者相反，你只需要理解它的本质是 \nabla_jw(j,i) 和 \nabla_jw(j,i-1) 的大小关系以及它如何推出决策单调性就行了。下面将会讲解这方面的内容。

决策单调性

对于一般情形的最大化线性 DP，可以表示为

f_i=\max_{0\le j<i}w(j,i)

其中 w(j,i) 是一个与 j 和 i 有关的函数，可以依赖 f_j 也可以不依赖。

我们称所有的 j,0\le j<i 都为 i 的决策点，其中令 w(j,i) 取得最大值的 j 称为最优决策点。称每个 i 为转移点。

此时如果当 i 单调递增时，最优决策点 j 存在一种选择是单调不降的，那么称这个转移具有决策单调性。这里标粗的字的意思是，每个 i 都有可能有多个最优决策点，而决策单调性只保证存在一种给每个 i 选择其中一个最优决策点的方式，使得最优决策点是单调不降的。

注意决策单调性只保证了最优决策点是单调的，其它决策点间的关系没有任何保证。

完全单调性

对于任意一组 S=\{i_1,i_2,\cdots\}，如果再任取一组它们的共同决策点 T=\{j_1,j_2,\cdots\}，并且限制所有 i 的决策点选择范围为 T，此时 S 中的 i 满足决策单调性，那么称这个转移具有完全单调性。换句话说，就是无论怎么限制决策点的范围，转移依旧具有决策单调性。

具有完全单调性的转移显然也具有决策单调性。

蒙日性

蒙日性其实就是四边形不等式性，只不过换了个名字，你想叫它四边形不等式性也没有问题。如果函数 w 满足四边形不等式，那么称这个转移具有蒙日性。

:::info[定理]{open}

具有蒙日性的转移同时具有完全单调性

:::

:::info[证明]{open}

尝试从这个形式入手：

w(j,i)-w(j-1,i)\ge w(j,i-1)-w(j-1,i-1)

这个形式保证了一件事：如果在 i-1 处决策点 j 优于 j-1，也就是 w(j,i-1)-w(j-1,i-1)\ge 0，那么在 i 处决策点 j 也优于决策点 j-1。反之如果 i 处 j-1 优于 j，那么 i-1 处 j-1 也优于 j。这个结论可以轻易地推到把 j-1 替换成任意比 j 小的决策点，把 i-1 替换成任意在 i 前的转移点。

现在考虑完全单调性的定义。任取了一个 S 和对应的 T，对于任意在 S 中的两个 i_1,i_2,i_1<i_2，其对应最优决策点为 j_1,j_2，那么在 i_1 处 j_1 不劣所有在它之前的决策点，于是在 i_2 处该性质仍然成立，于是如果 j_1\not=j_2，只有可能在 j_1 后面。完全单调性得证。

:::

算法

当动态规划的转移方程满足上面的部分性质时，就可以利用它来优化转移。

注：下面的算法代码求的都是最大值，最小值只需要把部分符号反向即可。

分治

适用于 w(j,i) 不依赖于 f_j 的情况，w 可以只支持移动访问，只要求转移具有决策单调性。

要求解所有 f_i，等价于求出每个 i 的最优决策点。如果已知一个 i 的最优决策点为 j，那么在 i 前的点的最优决策点在 j 之前（包含 j），在 i 之后的最优决策点在 j 之后（包含 j）。

于是分治过程中维护最优决策点的上下界，取转移点区间的中点暴力求出其最优决策点，然后向左右两侧分治即可。这样每一层至多调用 2n 次计算 w 的函数，如果 w 可以 \mathcal O(1) 计算，则总复杂度为 \mathcal O(n\log n)。

:::success[代码]

int calc(int, int);

// l,r 表示转移点区间，L,R 表示决策点区间
void solve(int l, int r, int L, int R) {
    if (l > r) return;
    int mid = (l + r) >> 1, pos = -1, res = 0;
    // 暴力查找 mid 位置的最优决策点
    for (int i = L; i <= R && i < mid; i++)
        if (!~pos || res < calc(i + 1, mid))
            pos = i, res = calc(i + 1, mid);
    f[mid] = res;
    solve(l, mid - 1, L, pos), solve(mid + 1, r, pos, R);
}

:::

:::info[w 只支持移动访问的情形] 当 w 只支持移动访问时，也就是 w 难以直接计算，但是从 w(j,i) 可以快速推出 w(j\pm 1,i) 和 w(j,i\pm 1) 时，可以采用类似莫队的方法来计算 w。此时复杂度仍然为 \mathcal O(n\log n) 的。每一层内转移和层间转移都只会调用 \mathcal O(R-L) 次 w 函数。

于是只需要把 cost 函数改为下面这样：

int cl, cr, cans;

void mov(int, bool);

int calc(int l, int r) {
    while (cl > l) mov(--cl, 1);
    while (cr < r) mov(++cr, 1);
    while (cl < l) mov(cl++, 0);
    while (cr > r) mov(cr--, 0);
    return cans;
}

:::

二分队列

适用于 w(j,i) 可以依赖 f_j 的情况，w 必须支持随机访问，要求转移具有完全单调性。

我们动态维护一个队列，每个元素形如 (l,r,j)，表示考虑当前加入过的决策点，位于 [l,r] 中的转移点的最优决策点是 j。这个做法需要完全单调性的原因是，如果只有决策单调性，那么加入一部分 j 时决策点间没有任何性质，于是无法保证每个决策点的更新是一段区间。

查询时把过时的元素（r<i）弹掉即可。考虑如何插入一个新的决策点 j。首先 j 要么没用，要么控制着一段转移点的后缀，那么只有队列尾部的一些区间可能因为 j 被弹掉。设此时尾部的元素为 (l,r,j')，如果在转移点 l 处 j' 都不优于 j，那么这个元素就没有存在的必要了，可以直接弹掉；如果 r 处 j' 优于 j，那么 j 无法替换掉 j'，退出循环；否则我们需要找到一个点 p，使得 [l,p-1] 中 j' 优于 j，[p,r] 中 j 不劣于 j'，这一步可以用二分来实现，然后跳出循环。

:::success[代码]

struct QNode { int l, r, v; };
struct Queue {
    QNode q[XN]; int hh, tt;
    void init() { hh = tt = 0; }
    bool em() { return hh == tt; }
    QNode& h() { return q[hh]; }
    QNode& t() { return q[tt - 1]; }
    void pph() { hh++; }
    void ppt() { tt--; }
    void pst(const QNode& val) { q[tt++] = val; }
} q;

int calc(int, int);

for (int i = 1; i <= n; i++) {
    while (q.h().r < i) q.pph();
    f[i] = cost(q.h().v, i);
    if ((q.h().l = i + 1) > q.h().r) q.pph();
    while (!q.em() && cost(q.t().v, q.t().l) <= cost(i, q.t().l)) q.ppt();
    if (q.em()) q.pst(QNode{i + 1, n, i});
    else if (cost(q.t().v, q.t().r) <= cost(i, q.t().r)) {
        int l = q.t().l, r = q.t().r;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (cost(q.t().v, mid) <= cost(i, mid)) r = mid;
            else l = mid + 1;
        }
        if ((q.t().r = l - 1) < q.t().l) q.ppt();
        q.pst(QNode{l, n, i});
    } else if (q.t().r < n)
        q.pst(QNode{q.t().r + 1, n, i});
}

:::

简化 LARSCH 算法

适用于 w(j,i) 可以依赖 f_j 的情况，同时 w 可以只支持移动访问，要求转移具有完全单调性。

这是一种分治算法。设当前对转移点区间 (l,r] 进行分治。

在进入函数时，需要求出 i\in[1,l] 的 f_i 和最优决策点 j_i，以及只考虑 [1,l] 间的决策点时转移点 r 的最优决策点 j_r'。在退出函数时，(l,r] 中的所有转移点都已经得到答案。

我们先找出转移点终点 mid。为了递归下去，我们需要知道 j_{mid}'。因为完全单调性，在考虑 [1,l] 间的决策点时，有 j_l\le j_{mid}'\le j_r'，所以只需要遍历 [j_l,j_r'] 中的决策点就可以求出 j_{mid}'。于是就可以递归向 (l,mid]。接下来还要向右侧递归，于是需要新的 j_r'，只需要遍历 (l,mid] 完成更新，最后向右侧 (mid,r] 递归。

算法的正确性在上面的过程中已经说明。首先递归层数是 \mathcal O(\log n) 层的；因为 [j_l,j_r'] 被划分为了 [j_l,j_{mid}'] 和 [j_{mid},j_r]，其中 j_l\le j_{mid}'\le j_{mid}\le j_r，因此每一层 [j_l,j_r'] 的总长度之和是 \mathcal O(n) 的；扫描 (l,mid] 这一步每一层显然总代价为 \mathcal O(n)。于是最终复杂度也是 \mathcal O(n\log n) 的了。

注意：因为函数需要的条件，调用分治函数前，要用最左端先更新一次最右端。

当 w 只支持移动访问时，使用分治算法同样的解决方式。复杂度的证明方式差不多，总之仍然是 \mathcal O(n\log n) 的。

:::success[代码]

int f[XN], fr[XN];

int cost(int, int);

void upd(int j, int i) {
    if (!~fr[i] || f[i] < cost(j, i))
        fr[i] = j, f[i] = cost(j, i);
}

// 记得调用整体函数前要先调用一次 upd(l, r)
void solve(int l, int r, int dep = 0) {
    if (l >= r) return;
    int mid = (l + r + 1) >> 1;
    for (int i = fr[l]; i <= fr[r] && i < mid; i++) upd(i, mid);
    if (mid < r) solve(l, mid, dep + 1);
    for (int i = l; i < mid; i++) upd(i, r);
    if (l < mid) solve(mid, r, dep + 1);
}

:::

这种算法相对于二分队列，虽然可以处理只支持移动访问的情况，但是却不如二分队列灵活，有些题目无法使用。比如下面的第三道例题。

例题

P4767 [IOI 2000] 邮局 加强版

:::info[题目链接]{open}

$n\le 3000,m\le 300

:::

我们在 dp 时可以放松限制，给一个区间的村庄钦定一个邮局，不要求每个状态下村庄的最小邮局都是给它钦定的邮局，因为这样不优，不会称为最终答案。

首先列出暴力 dp：设 f_{k,i} 表示放了 k 个邮局，考虑了前 i 个村庄时这些村庄到钦定邮局的距离和的最小值。于是有转移

f_{k,i}=\min_{j<i}\{f_{k-1,j}+w(j+1,i)\}

其中 w(j+1,i) 表示在 [j+1,i] 的村庄中放一个邮局，这些村庄到这个钦定邮局的距离和的最小值。这可以用区间 dp \mathcal O(n^2) 地预处理出来，或者预处理前缀和直接算。

暴力转移复杂度是 \mathcal O(n^2) 的，不可接受。考虑证明 w 满足四边形不等式。这里需要的形式是 w(j-1,i)-w(j,i)\ge w(j-1,i-1)-w(j,i-1)。相比于 i-1，i 位置多了一个村庄 i，因此 [j-1,i] 的中位数要么不动要么向右移动了一段距离，这样新加入的 j-1 显然应该产生更多的贡献，因此上面的四边形不等式成立。于是对于 i，决策点 j 单调向右移动，这里 f_k 只依赖于 f_{k-1}，因此使用分治即可。时间复杂度 \mathcal O(nm\log n)。

:::success[代码]

#include <algorithm>
#include <iostream>

using namespace std;

constexpr int inf = 0x3f3f3f3f;
constexpr int N = 3000, M = 300;
constexpr int XN = N + 10, XM = M + 10;
int n, m, a[XN], w[XN][XN];
int f[XN], g[XN];

void solve(int l, int r, int L, int R) {
    if (l > r) return;
    int mid = (l + r) >> 1, pos = -1, res = 0;
    for (int i = L; i <= R && i < mid; i++)
        if (!~pos || res > g[i] + w[i + 1][mid])
            pos = i, res = g[i] + w[i + 1][mid];
    f[mid] = res;
    solve(l, mid - 1, L, pos), solve(mid + 1, r, pos, R);
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + n + 1);
    for (int i = 1; i < n; i++)
        w[i][i + 1] = a[i + 1] - a[i];
    for (int len = 3; len <= n; len++)
        for (int l = 1, r = len; r <= n; l++, r++)
            w[l][r] = w[l + 1][r - 1] + a[r] - a[l];
    f[0] = 0;
    for (int i = 1; i <= n; i++) f[i] = inf;
    for (int i = 1; i <= m; i++) {
        for (int j = 0; j <= n; j++) g[j] = f[j];
        solve(1, n, 0, n);
    }
    cout << f[n] << endl;
    return 0;
}

:::

P5574 [CmdOI2019] 任务分配问题

:::info[题目链接]{open}

给定一个长度为 n 的排列，求将其划分为 k 段，每段内顺序对数量个数和的最小值。

1\le n\le 2.5\times 10^4,1\le k\le 25

:::

可以简单地列出朴素动态规划：设 f_{k,i} 表示把前 i 项分成 k 段，每段内顺序对数量个数和的最小值。有转移：

f_{k,i}=\min_{j<i}\{f_{k-1,j}+w(j+1,i)\}

其中 w(j+1,i) 表示 a_{j+1\sim i} 中的顺序对数量。

暴力转移无法接受，考虑优化。观察到 w 满足如下的四边形不等式：

w(j-1,i)-w(j,i)\ge w(j-1,i-1)-w(j,i-1)

证明是显然的：在 i 处加入 a_{j-1} 相比于 i-1 处会增加 a_i 和 a_{j-1} 的贡献，因此 i 处差分更大。

于是 f 的转移满足决策单调性，本题 f_k 仅依赖于 f_{k-1}，使用分治即可。这里 w 的计算牵扯到区间逆序对，不好直接做，但是可以用树状数组做到 \mathcal O(\log n) 的移动访问，于是移动访问配合分治即可，时间复杂度 \mathcal O(nk\log n)。

:::success[代码]

#include <cstdint>
#include <iostream>

using namespace std;

using ll = int64_t;

template<int N>
struct BIT {
    static constexpr int XN = N + 10;
    int n, c[XN];
    void update(int k, int x) { for (; k <= n; k += k & -k) c[k] += x; }
    int query(int k) { int res = 0; for (; k; k -= k & -k) res += c[k]; return res; }
    int query(int l, int r) { return query(r) - query(l - 1); }
};

constexpr ll inf = 0x3f3f3f3f;
constexpr int N = 2.5e4;
constexpr int XN = N + 10;
int n, m, a[XN];
BIT<N> bit;
int cl, cr; ll cans;
ll f[XN], g[XN];

void mov(int p, bool side, bool flag) {
    if (side) {
        if (flag) cans += bit.query(1, a[p] - 1), bit.update(a[p], 1);
        else      cans -= bit.query(1, a[p] - 1), bit.update(a[p], -1);
    } else {
        if (flag) cans += bit.query(a[p] + 1, n), bit.update(a[p], 1);
        else      cans -= bit.query(a[p] + 1, n), bit.update(a[p], -1);
    }
}

int calc(int l, int r) {
    while (cl > l) mov(--cl, 0, 1);
    while (cr < r) mov(++cr, 1, 1);
    while (cl < l) mov(cl++, 0, 0);
    while (cr > r) mov(cr--, 1, 0);
    return cans;
}

void solve(int l, int r, int L, int R) {
    if (l > r) return;
    int mid = (l + r) >> 1, pos = -1, res = 0;
    for (int i = L; i <= R && i < mid; i++)
        if (!~pos || res > g[i] + calc(i + 1, mid))
            pos = i, res = g[i] + calc(i + 1, mid);
    f[mid] = res;
    solve(l, mid - 1, L, pos), solve(mid + 1, r, pos, R);
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n >> m, bit.n = n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    cl = 1, cr = 0;
    for (int i = 0; i <= n; i++)
        f[i] = i ? inf : 0;
    for (int k = 1; k <= m; k++) {
        for (int i = 1; i <= n; i++) g[i] = f[i];
        solve(1, n, 0, n);
    }
    cout << f[n] << endl;
    return 0;
}

:::

P10538 [APIO2024] 星际列车

:::info[题目链接]{open}

有 n 个行星，和 m 条穿梭于这 n 个点间的列车；第 i 辆列车在时间 A[i] 在行星 X[i] 出发，在时间 B[i] 到达行星 Y[i]，票价为 C[i]。你有 w 顿饭要吃，其中第 i 顿饭可以在 [L[i],R[i]] 的时间区间内吃，吃饭没有顺序要求。在列车上吃饭不花钱，在第 i 个行星上吃一顿饭的代价为 T[i]。求 0 时刻出发从 1 号行星到 n 号行星，吃完所有饭的最小总花费代价。

2\le n,m,w\le 10^5

:::

考虑如何设计状态。状态需要包含两个信息：当前在哪个行星，以及当前的时刻。因为每条列车有固定的发车和到站时间，以及固定的起始点，因此我们可以用当前经过的最后一条列车来表示状态。

具体的，设 f_i 表示刚刚经过编号为 i 的边，当前在 Y[i]，考虑了 R 在 A[i] 之前的饭的最小总代价。那么可以容易地列出转移：

f_i=C[i]+\min_{j,B[j]\le A[i]\land Y[j]=X[i]}\{f_j+w(B[j]+1,A[i]-1)\}

其中 w(B[j]+1,A[i]-1) 表示只能在 [B[j]+1,A[i]-1] 中吃的饭的个数，即包含于 [B[j]+1,A[i]-1] 的 [L[k],R[k]] 个数。

观察 w，不难发现其满足四边形不等式：

w(j-1,i)-w(j,i)\ge w(j-1,i-1)-w(j,i-1)

证：考虑在 i 处和 i-1 处分别扩展左端点到 j-1，于是 i-1 处的贡献完全包含于 i 处扩展，而 i 处会多一些 L\in[j-1,i],R=i 的区间，因此会带来更多贡献。因此上式成立。

于是如果在 i-1 处 j 优于 j-1，那么在 i 处 j 仍然优于 j-1。也就是说对于 X[i] 相同的 i，最优决策点 j 的 B[j] 具有单调性。

于是把边按 A 和 B 分别升序排序成两个序列，在第一个序列中枚举转移点，在第二个序列枚举决策点。对每个行星建一个二分队列，f_i 从 X[i] 处的二分队列更新，然后用 f_i 更新 Y[i] 处的二分队列。求 w 用一个主席树，总时间复杂度 \mathcal O((n+m)\log^2m)。实现可以参考下面的代码。

注意：虽然这里 w 移动访问可以单 \log 求，但是却不能使用简化 LARSCH 算法，因为这里不是序列上的问题，不同节点间的单调队列转移有依赖。

:::success[代码]

#include <algorithm>
#include <cassert>
#include <cstdint>
#include <cstring>
#include <iostream>
#include <vector>

using namespace std;

using vec = vector<int>;

namespace xuezy {
    using ll = int64_t;

    constexpr int inf = 0x3f3f3f3f;
    constexpr int N = 1e5, N4 = N * 4, M = N * 40;
    constexpr int XN = N + 10, XN4 = N4 + 10, XM = M + 10;
    int n, m, c, len, cnt[XN]; ll val[XN];
    struct Edge { int u, v, w, s, t, id; } ed[XN], ef[XN], eg[XN];
    struct Data { int l, r, id; };
    struct Queue {
        vector<Data> q; int hh, tt;
        inline bool em() { return hh == tt; }
        inline Data& h() { return q[hh]; }
        inline Data& t() { return q[tt - 1]; }
        inline void pst(const Data& val) { q[tt++] = val; }
        inline void ppt() { tt--; }
        inline void pph() { hh++; }
    } qq[XN];
    ll f[XN];

    void uniq(vec& a_in, vec& b_in, vec& l_in, vec& r_in) {
        static int b[XN4]; len = 0;
        b[++len] = 0, b[++len] = inf;
        for (int i = 0; i < m; i++)
            b[++len] = a_in[i], b[++len] = b_in[i];
        for (int i = 0; i < c; i++)
            b[++len] = l_in[i], b[++len] = r_in[i];
        sort(b + 1, b + len + 1), len = unique(b + 1, b + len + 1) - b - 1;
        for (int i = 0; i < m; i++)
            a_in[i] = lower_bound(b + 1, b + len + 1, a_in[i]) - b,
            b_in[i] = lower_bound(b + 1, b + len + 1, b_in[i]) - b;
        for (int i = 0; i < c; i++)
            l_in[i] = lower_bound(b + 1, b + len + 1, l_in[i]) - b,
            r_in[i] = lower_bound(b + 1, b + len + 1, r_in[i]) - b;
    }

    struct SegmentTree {
        #define mid ((l + r) >> 1)

        int rt[XN4], idx;
        struct Pos { int x, y; } p[XN];
        struct Node { int ls, rs, sum; } e[XM];
        vector<int> pv[XN4];

        void pushup(int u) { e[u].sum = e[e[u].ls].sum + e[e[u].rs].sum; }

        int update(int v, int pos, int val, int l = 1, int r = len) {
            int u = ++idx; assert(u < M); e[u] = e[v];
            if (l == r) return e[u].sum += val, u;
            if (pos <= mid) e[u].ls = update(e[v].ls, pos, val, l, mid);
            else            e[u].rs = update(e[v].rs, pos, val, mid + 1, r);
            return pushup(u), u;
        }

        int _query(int u, int v, int ql, int qr, int l = 1, int r = len) {
            if (ql <= l && r <= qr) return e[v].sum - e[u].sum;
            if (qr <= mid) return _query(e[u].ls, e[v].ls, ql, qr, l, mid);
            if (ql > mid)  return _query(e[u].rs, e[v].rs, ql, qr, mid + 1, r);
            return _query(e[u].ls, e[v].ls, ql, qr, l, mid)
                 + _query(e[u].rs, e[v].rs, ql, qr, mid + 1, r);
        }

        void init() {
            idx = 0, rt[0] = 0;
            for (int i = 1; i <= c; i++)
                pv[p[i].x].push_back(p[i].y);
            for (int i = 1; i <= len; i++) {
                rt[i] = rt[i - 1];
                for (int j : pv[i])
                    rt[i] = update(rt[i], j, 1);
            }
        }

        inline int query(int x1, int x2, int y1, int y2) {
            if (x1 > x2 || y1 > y2) return 0;
            return _query(rt[x1 - 1], rt[x2], y1, y2);
        }

        inline int query(int l, int r) {
            return query(l, r, l, r);
        }

        #undef mid
    } seg;

    inline ll cost(int j, int i, int u) {
        return f[j] + val[u] * seg.query(ed[j].t + 1, i - 1);
    }

    void movupd(const Edge& ed) {
        if (f[ed.id] == inf) return;
        int tar = ed.v, tim = ed.t; Queue& q = qq[tar];
        if (!q.em() && q.h().r < tim) q.pph();
        if (!q.em()) q.h().l = tim;
        while (!q.em() && cost(q.t().id, q.t().l, tar) >= cost(ed.id, q.t().l, tar)) q.ppt();
        if (q.em()) q.pst(Data{tim, len, ed.id});
        else if (cost(q.t().id, q.t().r, tar) >= cost(ed.id, q.t().r, tar)) {
            int l = q.t().l, r = q.t().r;
            while (l < r) {
                int mid = (l + r) >> 1;
                if (cost(q.t().id, mid, tar) >= cost(ed.id, mid, tar)) r = mid;
                else l = mid + 1;
            }
            if ((q.t().r = l - 1) < q.t().l) q.ppt();
            q.pst(Data{l, len, ed.id});
        } else if (q.t().r < len)
            q.pst(Data{q.t().r + 1, len, ed.id});
    }

    void movqry(const Edge& ed) {
        int tar = ed.u, tim = ed.s; Queue& q = qq[tar];
        while (!q.em() && q.h().r < tim) q.pph();
        if (!ed.id) f[ed.id] = 0;
        else if (q.em()) f[ed.id] = inf;
        else f[ed.id] = cost(q.h().id, tim, tar) + ed.w;
    }

    ll solve(int n_in, int m_in, int w_in, vec t_in, vec x_in, vec y_in, vec a_in, vec b_in, vec c_in, vec l_in, vec r_in) {
        n = n_in, m = m_in, c = w_in;
        uniq(a_in, b_in, l_in, r_in);
        for (int i = 1; i <= n; i++)
            val[i] = t_in[i - 1];
        for (int i = 1; i <= m; i++)
            ed[i] = Edge{x_in[i - 1] + 1, y_in[i - 1] + 1, c_in[i - 1], a_in[i - 1], b_in[i - 1], i};
        for (int i = 1; i <= c; i++)
            seg.p[i] = SegmentTree::Pos{l_in[i - 1], r_in[i - 1]};
        seg.init();
        for (int i = 1; i <= n; i++) cnt[i] = 0;
        ed[0] = Edge{1, 1, 0, 1, 1, 0}, cnt[1]++;
        ++m, ed[m] = Edge{n, n, 0, len, len, m}, cnt[n]++;
        for (int i = 0; i <= m; i++)
            ef[i] = eg[i] = ed[i], cnt[ed[i].v]++;
        for (int i = 1; i <= n; i++) qq[i].q.resize(cnt[i]);
        sort(ef + 0, ef + m + 1, [](const Edge& i, const Edge& j) { return i.t < j.t; });
        sort(eg + 0, eg + m + 1, [](const Edge& i, const Edge& j) { return i.s < j.s; });
        for (int i = 0, j = 1; i < m || j <= m; ) {
            if (j > m || (i < m && ef[i].t <= eg[j].s))
                movupd(ef[i++]);
            else movqry(eg[j++]);
        }
        return f[m] == inf ? -1 : f[m];
    }
};

long long solve(int N, int M, int W, vec T, vec X, vec Y, vec A, vec B, vec C, vec L, vec R) {
    return xuezy::solve(N, M, W, T, X, Y, A, B, C, L, R);
}

:::