题解 P5471 【[NOI2019]弹跳】

题目大意

给出二维平面上的 n 个整点 (x_i,y_i) ，满足 1\le x_i\le w,1\le y_i\le h 。按给出顺序编号为 1,2,...,n 。有 m 次连边操作，每次操作给定 p,t,L,R,D,U ，从结点 p 到满足条件 L\le x_i\le R,D\le y_i\le U 的所有这样的结点 i 连接一条边权为 t 的有向边。求在所有连边操作结束后，从编号为 1 的点到其他点的最短路长度。

1\le w,h\le n\le 70000,1\le m\le 150000,1\le t_i\le 10000

32pts

暴力连边，边数最多为 O(nm) ，跑最短路。

暴力分还挺多

L_i=R_i,D_i=U_i

观察到每次连边操作只会连接两个结点，暴力连边，边数为 O(m) ，跑最短路。

什么，还有其他最短路算法？

h=1

开题一看，这不是 线段树优化建图 的题吗？

线段树优化建图，是图论问题中的经典技巧。将所有点按照 x 坐标排序，观察到每次连边操作连接到的点都是连续的一段。

（图片来源： NaCly_Fish ）

我们对排序后的序列建一棵线段树，线段树上的每个结点向其左右儿子连一条边权为 0 的边，每个叶子结点向其对应位置的点连一条边权为 0 的边。在进行连边操作时，用类似于线段树上区间查询的方式向所有对应的点连一条边。根据线段树的经典结论，这样所连的边数最多是 O(\log_2 n) 的。

总点数为 O(n) ，总边数为 O(n+m\log_2 n) ，可以存下所有的边，跑最短路即可。

线段树优化建图的经典题目：

CF786B Legacy

P5025 [SNOI2017]炸弹

100pts

现在连边从原来的一维变成二维的了。

在做这题时，我考虑了分块套分块，分块套线段树，线段树套线段树等多种方法，最后发现线段树套动态开点线段树比较优秀。

外层 x 坐标用普通线段树，这棵线段树上每个结点都对应一个关于 y 坐标的线段树，线段树上存储的是所有 x 坐标在范围内的点。由于内层动态开点线段树插入一个值的空间复杂度为 O(\log_2 n) ，外层线段树有 O(\log_2 n) 层，所以总的点数为 O(n\log_2^2 n) 。

连边时，先找到 O(\log_2 n) 个关于 x 坐标的区间对应的点，然后对这 O(\log_2 n) 棵线段树查询下标范围在 y 坐标范围内的值。单次连接的边数为 O(\log_2^2 n) ，总的边数为 O(m\log_2^2 n) 。

然而，这种写法的内存使用超过了限制。一般的实现可以得到 64 到 72 分。有以下两个优化方法：

1. 树套树内层使用 n 个结点时空间复杂度是 O(n) 的 set 容器；

2. 不直接连边 。回顾 Dij 的算法流程，有如下写法：用线段树套 set 维护一个矩阵中存在的整点，开始时扩展 1 号结点的所有出边（直接连接到一个矩阵），每次取出优先队列中时间最小的一个矩阵，遍历矩阵中的每一个存在的整点，记录到这些点的最短路，扩展这些结点，然后在线段树套 set 上删除这些结点。由于每个结点只会被删除和扩展一次，所以这样做的时间复杂度是 O(n\log_2^2 n) 的。

同时使用两种优化，时间复杂度是 O(n\log_2^2 n) ，空间复杂度是 O(n\log_2 n+m) 的，可以通过本题。

代码展示

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<set>
#include<vector>
#include<queue>
using namespace std;
const int maxn=150010;
int n,m,W,H;
struct city{int id,x,y;bool operator<(city a)const{return y==a.y?id<a.id:y<a.y;};}s[maxn];
set<city>st[maxn*2];
#define lc (o<<1)
#define rc (o<<1|1)
void update(int o,int l,int r,int v)
{
    st[o].insert(s[v]);
    if(l==r)return;
    int mid=(l+r)>>1;
    if(s[v].x<=mid)update(lc,l,mid,v);
    else update(rc,mid+1,r,v);
}
void deleet(int o,int l,int r,int v)
{
    st[o].erase(s[v]);
    if(l==r)return;
    int mid=(l+r)>>1;
    if(s[v].x<=mid)deleet(lc,l,mid,v);
    else deleet(rc,mid+1,r,v);
}
struct jumpy{int p,t,l,r,d,u;}e[maxn];
vector<int>g[maxn];
struct node{int x,v;bool operator<(node a)const{return v>a.v;};}x;
priority_queue<node>q;
queue<int>tag;
int dist[maxn];
bool tf[maxn];
void erasse(int o,int l,int r,int id,int v)
{
    int ql=e[id].l,qr=e[id].r;
    if(r<ql||l>qr)return;
    if(ql<=l&&r<=qr)
    {
        set<city>::iterator lb=lower_bound(st[o].begin(),st[o].end(),(city){0,n+1,e[id].d});
        for(;lb!=st[o].end()&&(lb->y)<=e[id].u;lb++)
        {
            dist[lb->id]=v;tag.push(lb->id);
            for(vector<int>::iterator it=g[lb->id].begin();it!=g[lb->id].end();it++)q.push({*it,v+e[*it].t});
        }
        while(!tag.empty())deleet(1,1,n,tag.front()),tag.pop();
        return;
    }
    int mid=(l+r)>>1;
    erasse(lc,l,mid,id,v);erasse(rc,mid+1,r,id,v);
}
int main()
{
    scanf("%d%d%d%d",&n,&m,&W,&H);
    for(int i=1;i<=n;i++)scanf("%d%d",&s[i].x,&s[i].y),s[i].id=i,update(1,1,n,i);
    for(int i=1;i<=m;i++)scanf("%d%d%d%d%d%d",&e[i].p,&e[i].t,&e[i].l,&e[i].r,&e[i].d,&e[i].u),g[e[i].p].push_back(i);
    e[0].l=e[0].r=s[1].x;e[0].d=e[0].u=s[1].y;
    q.push({0,0});
    while(!q.empty())
    {
        x=q.top();q.pop();
        if(tf[x.x])continue;
        tf[x.x]=true; 
        erasse(1,1,n,x.x,x.v);
        //for(vector<int>::iterator it=g[x.x].begin();it!=g[x.x].end();it++)q.push({e[*it].p,x.v+e[*it].t});
    }
    for(int i=2;i<=n;i++)printf("%d\n",dist[i]);
    return 0;
}