题目大意

给出二维平面上的 $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;
}