专栏文章

题解：AT_abc232_g [ABC232G] Modulo Shortest Path

GGGapa
AT_abc232_g题解参与者 3已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@mir23c5j
此快照首次捕获于
2025/12/04 14:29
3 个月前
此快照最后确认于
2025/12/04 14:29
3 个月前
查看原文

[ABC232G] Modulo Shortest Path

https://www.luogu.com.cn/problem/AT_abc232_g
一个使用了最短路的思想但是并没有使用任何最短路的数据结构题解。
考虑 Dijkstra 暴力跑这个问题是怎么实现的，djk 每次会选择一个离起点集最近的点然后将其加入点集，由于题目中图是完全图，图中每个点都有可能是离起点最近的点，这启示我们用数据结构寻找全局最小值然后将其加入点集。
考虑具体怎么做，首先如果一个节点已经被加入点集，那么他的权值应当为 ∞\infty，这一点是毋庸置疑的。
接着我们考虑从每一个节点出发，能够对未加入点集中的点造成什么样的影响。设当前加入点集的节点为 uu，当前节点最短路为 f(u)f(u)，分两种情况讨论，若 bv+au<mb_v + a_u < m，则 f(v)←min⁡(f(v),f(u)+au+bv)f(v) \gets \min(f(v), f(u) + a_u + b_v)，否则 f(v)←min⁡(f(v),f(u)+au+bv−m)f(v) \gets \min(f(v), f(u) + a_u + b_v - m)，我们是可以提前将每个节点通过 bb 从小到大排序，这样每次操作我们可以二分出第一个 au+bv≥ma_u + b_v \ge m 的位置 pospos，用 f(u)+au−mf(u) + a_u - m 对 [pos,n][pos, n] 取最小值，由于后者如果存在一定比前者优，用 f(u)+auf(u) + a_u 对全局取最小值。
现在我们已经可以使用线段树解决这个问题了，对于每个区间，分别记录最小值、最小值位置、最小的 bb 值，最小 bb 所在位置，即可维护这个问题。
由于笔者想题的时候 nt 了，所以求的是 n→1n \to 1 的最短路，核心和上述思路一样。
CPP
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a), stOwxc = (b); i <= stOwxc; i++)
#define per(i, a, b) for(int i = (a), stOwxc = (b); i >= stOwxc; i--)
using namespace std;
using LL = long long;
using VI = vector<int>;
const int N = 2e5 + 5;
const LL INF = 1e18;

int A[N], B[N], id[N], exc[N];
int mod;

#define ls (x << 1) 
#define rs ((x << 1) | 1)
namespace SGT {   
    static const int N = (int)2e5 << 2;
    struct Node {
        int minapos, minvpos;
        LL tag, minval, mina;
    }tr[N];
    int n;
    void pushup(int x) {
        tr[x].minval = min(tr[ls].minval, tr[rs].minval);
        tr[x].mina = min(tr[ls].mina, tr[rs].mina);
        tr[x].minvpos = tr[ls].minval <= tr[rs].minval ? tr[ls].minvpos : tr[rs].minvpos;
        tr[x].minapos = tr[ls].mina <= tr[rs].mina ? tr[ls].minapos : tr[rs].minapos;
    }
    void build(int x = 1, int l = 1, int r = n) {
        tr[x].tag = INF;
        if(l == r) return tr[x].mina = A[id[l]], tr[x].minapos = l, tr[x].minval = (id[l] == n ? 0 : INF), tr[x].minvpos = l,  void();
        int mid = l + r >> 1;
        build(ls, l, mid); build(rs, mid + 1, r);
        pushup(x);
    }   
    void init(int nn) {
        n = nn; 
        build();
    }
    void apply(int x, LL v) {
        tr[x].tag = min(tr[x].tag, v);
        if(v + tr[x].mina < tr[x].minval) tr[x].minval = tr[x].mina + v, tr[x].minvpos = tr[x].minapos;
    }
    void pushdown(int x) {
        if(tr[x].tag == INF) return;
        apply(ls, tr[x].tag); apply(rs, tr[x].tag);
        tr[x].tag = INF;
    }
    void modify(int L, int R, LL v, int l = 1, int r = n, int x = 1) {
        if(L <= l && r <= R) return apply(x, v);
        int mid = l + r >> 1;
        pushdown(x);
        if(L <= mid) modify(L, R, v, l, mid, ls);
        if(mid < R) modify(L, R, v, mid + 1, r, rs);
        pushup(x);
    }
    void del(int it, int x = 1, int l = 1, int r = n) {
        if(l == r) return tr[x].minval = tr[x].mina = INF,  void();
        int mid = l + r >> 1;
        pushdown(x);
        if(it <= mid) del(it, ls, l, mid);
        else del(it, rs, mid + 1, r); 
        pushup(x);
    }
}
#undef ls
#undef rs
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n; cin >> n >> mod;
    rep(i, 1, n) cin >> A[i] ;
    rep(i, 1, n) cin >> B[i];
    iota(id, id + 1 + n, 0);
    sort(id + 1, id + 1 + n, [](const int x, const int y) {
        return A[x] < A[y];
    });
    rep(i, 1, n) exc[i] = id[i];
    auto find = [&](LL v) {
        int l = 1, r = n, ret = 1;
        while(l <= r) {
            int mid = l + r >> 1, i = id[mid];
            if(A[i] + v >= mod) r = mid - 1, ret = mid;
            else l = mid + 1;
        }
        return ret;
    };
    SGT::init(n);
    vector<LL> F(n + 1);
    for(int o = 1; o <= n; o++) {
        int it = SGT::tr[1].minvpos, i = id[it];
        F[it] = SGT::tr[1].minval;
        SGT::del(it);
        SGT::modify(1, n, B[i] + F[it]);
        if(B[i] + A[id[n]] >= mod) SGT::modify(find(B[i]), n, B[i] + F[it] - mod);
    }
    rep(i, 1, n) if(id[i] == 1) return cout << F[i] << '\n', 0;
    return 0;
}

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...