题解：P9312 [EGOI 2021] Lanterns / 灯笼

UKE_Automation · 2025-04-06 17:29:52 · 题解

P9312 [EGOI 2021] Lanterns / 灯笼

\text{Link}

先考虑朴素的 dp 怎么做：枚举起点 i，然后令 dp(l,r) 表示此时合法海拔范围在 [l,r] 的最小花费。由于起点确定，海拔范围 [l,r] 表示的区间就确定了。转移的时候枚举区间中的灯笼，能转移当且仅当这个灯笼的 [A_i,B_i] 与 [l,r] 有交集。复杂度是 O(n^3 k) 的。

考虑优化，首先要优化的就是将枚举起点这一步搞掉，方法很简单，转置一手即可。然后由于起点未知，[l,r] 能表示的区间也就不知道了，所以还要记录区间中的一个点来转移。于是设 dp(l,r,i) 表示当前走到 i，合法范围在 [l,r]，从这个状态开始走完还需要的最小花费。

这样做其实没有优化复杂度，不过这时候的瓶颈就在状态上了。考虑怎样优化状态，我们想办法把海拔上下界和区间位置这两个信息压缩起来，这时候不难想到，由于上下界是由区间中某两个点确定的，所以只需要知道这两个点的位置，就可以计算出区间位置和上下界了。所以设 dp(u,v) 表示当前海拔下界为 A_u，海拔上界为 B_v，区间经过 u,v 还需要的最小花费。

考虑转移，枚举区间中的灯笼，然后依然判断交集并转移即可，分类讨论一下有：

此时的复杂度是 O(k^2 n) 的，瓶颈在转移。考虑如何优化，先看第一种转移。由于整个过程实际上还是类似区间 dp，所以我们在枚举的时候 u 应该按 A 从小到大枚举，v 应该按 B 从大到小枚举。这时候会发现，对于 B_j>B_i，如果 f(u,v') 无法转移到 f(u,j)，那么它同样不可能转移到 f(u,i)，原因显然。

于是我们就可以对 u 维护一个小根堆，存储所有还可以转移的 f(u,v')+W_{v'} 的值。当我们枚举到一个 f(u,v) 的时候，先弹出堆顶已经不能转移的 v'，然后此时的堆顶就是一个合法转移点，直接转移即可。这样的话对于同一个 u，每个 v 最多进堆一次，出堆一次，复杂度是 O(k\log k) 的，所以总复杂度就是 O(k^2\log k)。

对于第二种转移优化方式和第一种类似，不再赘述。现在看第三种转移，一个经典的思路是我们分步转移，也就是 f(p,p)\to f(p,v)/ f(u,p) \to f(u,v) 这样转移。这时会发现 f(p,v) 或者 f(u,p) 都是不合法的状态，不过问题不大，我们特判一下，把它们的值赋为 f(p,p) 即可。

如此我们的 dp 就优化到了 O(k^2 \log k)，可以通过。

#include <bits/stdc++.h>
#define il inline

using namespace std;

const int Maxn = 2e3 + 5;
const int Inf = 2e9 + 5;
const int Mod = 1e9 + 7;
il int Add(int x, int y) {return x + y >= Mod ? x + y - Mod: x + y;} il void pls(int &x, int y) {x = Add(x, y);}
il int Del(int x, int y) {return x - y < 0 ? x - y + Mod : x - y;} il void sub(int &x, int y) {x = Del(x, y);}
il int max(int x, int y) {return x >= y ? x : y;} il void chkmax(int &x, int y) {x = (x >= y ? x : y);}
il int min(int x, int y) {return x <= y ? x : y;} il void chkmin(int &x, int y) {x = (x <= y ? x : y);}
il int qpow(int a, int b) {int res = 1; for(; b; a = 1ll * a * a % Mod, b >>= 1) if(b & 1) res = 1ll * res * a % Mod; return res;}
il int Inv(int a) {return qpow(a, Mod - 2);}
template <typename T>
il void read(T &x) {
    x = 0; char ch = getchar(); bool flg = 0;
    for(; ch < '0' || ch > '9'; ch = getchar()) flg = (ch == '-');
    for(; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
    flg ? x = -x : 0;
}
template <typename T>
il void write(T x, bool typ = 1) {
    static short Stk[50], Top = 0;
    x < 0 ? putchar('-'), x = -x : 0;
    do Stk[++Top] = x % 10, x /= 10; while(x);
    while(Top) putchar(Stk[Top--] | 48);
    typ ? putchar('\n') : putchar(' ');
}
il void IOS() {ios::sync_with_stdio(0); cin.tie(0), cout.tie(0);}
il void File() {freopen("lantern.in", "r", stdin); freopen("lantern.out", "w", stdout);}
bool Beg;

int n, m, h[Maxn];
int p[Maxn], c[Maxn], a[Maxn], b[Maxn];
int id1[Maxn], id2[Maxn];
int l[Maxn][2], r[Maxn][2];
int dp[Maxn][Maxn];
#define pii pair<int, int>
#define mk make_pair
priority_queue <pii, vector<pii>, greater<pii>> q1[Maxn], q2[Maxn]; 

bool End;
il void Usd() {cerr << (&Beg - &End) / 1024.0 / 1024.0 << "MB " << (double)clock() * 1000.0 / CLOCKS_PER_SEC << "ms\n"; }
int main() {
    File();
    read(n), read(m);
    for(int i = 1; i <= n; i++) read(h[i]);
    for(int i = 1; i <= m; i++) read(p[i]), read(c[i]), read(a[i]), read(b[i]), id1[i] = id2[i] = i;
    sort(id1 + 1, id1 + m + 1, [](int x, int y){return a[x] < a[y];});
    sort(id2 + 1, id2 + m + 1, [](int x, int y){return b[x] > b[y];});
    for(int i = 1; i <= m; i++) {
        l[i][0] = l[i][1] = r[i][0] = r[i][1] = p[i];
        while(l[i][0] > 1 && h[l[i][0] - 1] >= a[i]) l[i][0]--;
        while(r[i][0] < n && h[r[i][0] + 1] >= a[i]) r[i][0]++;
        while(l[i][1] > 1 && h[l[i][1] - 1] <= b[i]) l[i][1]--;
        while(r[i][1] < n && h[r[i][1] + 1] <= b[i]) r[i][1]++;
    }
    for(int i = 1; i <= m; i++) { //最小值 
        for(int j = 1; j <= m; j++) { //最大值 
            int x = id1[i], y = id2[j];
            dp[x][y] = Inf;
            if(p[x] < l[y][1] || p[x] > r[y][1] || p[y] < l[x][0] || p[y] > r[x][0]) continue;
            if(a[y] < a[x] && b[x] > b[y]) continue;
            int pl = max(l[x][0], l[y][1]), pr = min(r[x][0], r[y][1]);
            if(pl == 1 && pr == n) dp[x][y] = 0;
            else if(a[y] < a[x]) dp[x][y] = dp[y][y];
            else if(b[x] > b[y]) dp[x][y] = dp[x][x];
            else {
                while(!q1[x].empty()) {
                    int t = q1[x].top().second;
                    if(p[t] < pl || p[t] > pr || b[t] < a[x] || a[t] > b[y]) q1[x].pop();
                    else break;
                }
                if(q1[x].size()) chkmin(dp[x][y], q1[x].top().first);
                while(!q2[y].empty()) {
                    int t = q2[y].top().second;
                    if(p[t] < pl || p[t] > pr || b[t] < a[x] || a[t] > b[y]) q2[y].pop();
                    else break;
                }
                if(q2[y].size()) chkmin(dp[x][y], q2[y].top().first);
            }
            if(dp[x][y] != Inf) {
                q1[x].push(mk(dp[x][y] + c[y], y));
                q2[y].push(mk(dp[x][y] + c[x], x));
            }
        }
    }
    for(int i = 1; i <= m; i++) {
        if(h[p[i]] < a[i] || h[p[i]] > b[i] || dp[i][i] == Inf) write(-1);
        else write(dp[i][i] + c[i]);
    }
    Usd();
    return 0;
}