LOJ 3159: 「NOI2019」弹跳

忘是亡心i 2021-10-30 03:08 236阅读 0赞

题目传送门：[LOJ \#3159][LOJ _3159]。

### 题意简述： ###

二维平面上有 \\(n\\) 个整点，给定每个整点的坐标 \\((x\_i,y\_i)\\)。  
有 \\(m\\) 种边，第 \\(i\\) 种边从 \\(p\_i\\) 号点连向满足 \\(l\_i\\le x\_j\\le r\_i\\) 和 \\(d\_i\\le y\_j\\le u\_i\\) 的点 \\(j\\)，即一个矩形范围内的所有点。

求 \\(1\\) 号点到其它每个点的最短路长度。

### 题解： ###

考虑 Dijkstra 算法求最短路的过程：  
一开始只有起点的距离为 \\(0\\)，而其它点距离为无限大。  
每次取出一个距离最短的没被更新过的点，用它更新它能到达的所有未被更新过的点的距离，并将其标记为已被更新。  
重复这个过程直到所有点均被更新。

上述过程一般使用单调队列来维护距离最短的点。  
而在此题中，一次更新时可能加入的点会有很多很多，不能每次将其一并加入。  
可以考虑加入一条边而非点，加入的这条边就代表了这条边连向的所有点的距离。  
类似地，每次取出距离最短的边，此时这条边代表的矩形内部的所有点均可以进行更新，因为只会去更新未被更新过的点，所以更新完这些点的距离后，可以把这些点全部删除。

上述方法是最短路中包含“一对多”，“多对多”的边时的处理办法。还有一种方法是使用数据结构模型优化建边，但是一般不会比这种方法来得优。

至于具体如何维护矩形删点操作，删点时可以暴力一个个删除，因为每个点只会被删除一次，问题在于如何快速找到要删除的点。  
这里我使用线段树套平衡树（`std::set`）维护，外层线段树处理横坐标上的区间，内层平衡树可以快速访问目标点将其删除。

下面是代码，时间复杂度为 \\(\\mathcal\{O\}(n\\log^2n+m\\log m)\\)：

#include <cstdio>
    #include <algorithm>
    #include <vector>
    #include <queue>
    #include <set>
    
    #define mp std::make_pair
    typedef std::pair<int, int> pii;
    typedef std::multiset<pii>::iterator iter;
    const int MN = 70005, MM = 150005;
    const int MS = 1 << 18 | 7;
    
    int N, M, W, H, yp[MN], vis[MN], dis[MN];
    int h[MN], nxt[MM], et[MM], eL[MM], eR[MM], eD[MM], eU[MM];
    std::multiset<pii> st[MS];
    std::priority_queue<pii> pq;
    void Ins(int i, int l, int r, int x, int id) {
        st[i].insert(mp(yp[id], id));
        if (l == r) return ;
        int mid = (l + r) >> 1;
        if (x <= mid) Ins(i << 1, l, mid, x, id);
        else Ins(i << 1 | 1, mid + 1, r, x, id);
    }
    void Del(int i, int l, int r, int id, int d) {
        if (r < eL[id] || eR[id] < l) return ;
        if (eL[id] <= l && r <= eR[id]) {
            iter it = st[i].lower_bound(mp(eD[id], 0)), tmp;
            while (it != st[i].end() && it -> first <= eU[id]) {
                int u = it -> second;
                if (!vis[u]) {
                    vis[u] = 1, dis[u] = d;
                    for (int j = h[u]; j; j = nxt[j])
                        pq.push(mp(-d - et[j], j));
                }
                tmp = it, ++it, st[i].erase(tmp);
            }
            return ;
        }
        int mid = (l + r) >> 1;
        Del(i << 1, l, mid, id, d);
        Del(i << 1 | 1, mid + 1, r, id, d);
    }
    
    int main() {
        freopen("jump.in", "r", stdin);
        freopen("jump.out", "w", stdout);
        scanf("%d%d%d%d", &N, &M, &W, &H);
        for (int i = 1, x; i <= N; ++i) {
            scanf("%d%d", &x, &yp[i]);
            Ins(1, 1, W, x, i);
        }
        for (int i = 1, p; i <= M; ++i) {
            scanf("%d%d%d%d%d%d", &p, &et[i], &eL[i], &eR[i], &eD[i], &eU[i]);
            nxt[i] = h[p], h[p] = i;
        }
        dis[1] = 0, vis[1] = 1;
        for (int i = h[1]; i; i = nxt[i])
            pq.push(mp(-et[i], i));
        while (!pq.empty()) {
            pii ed = pq.top(); pq.pop();
            int dis = -ed.first, id = ed.second;
            Del(1, 1, W, id, dis);
        }
        for (int i = 2; i <= N; ++i) printf("%d\n", dis[i]);
        return 0;
    }

转载于:https://www.cnblogs.com/PinkRabbit/p/NOI2019D2T1.html

[LOJ _3159]: https://loj.ac/problem/3159