题意

给定一个带权有向图（初始时有 $n$ 个顶点，没有边）。我们将构建一棵线段树来处理第二类查询（对于第三类查询也采用类似的方法，但方向相反）。

思路

在区间 $1, \dots, n$ 上建立一棵线段树。对于线段树的每个节点，我们在图中引入一个对应的顶点。对于线段树中的每个叶子节点（例如对应区间 $[l, l+1)$），添加一条从该节点对应的顶点到原图中顶点 $l$ 的边，边权为 $0$。对于每个非叶子节点，添加一条从该节点对应的顶点到其两个子节点对应顶点的边，边权也为 $0$。

这样，我们总共向图中添加了大约 $4n$ 个顶点和边。对于每个第二类查询，我们从顶点 $v$ 向线段树中所有覆盖区间 $[l, r)$ 的最大节点（每个查询对应 $\lg(n)$ 个节点）添加一条边，边权为 $w$。

对于第三类查询，我们以相同的方式构建另一棵线段树（方向相反）。最后，在这个图上运行 Dijkstra 算法。

算法步骤

1. 构建两棵线段树：一棵用于处理第二类查询（从原图顶点指向线段树节点），另一棵用于处理第三类查询（从线段树节点指向原图顶点）。
2. 对于第二类查询的线段树：
   • 每个叶子节点（对应区间 $[l, l+1)$）向原图顶点 $l$ 连一条边权为 $0$ 的边。
   • 每个非叶子节点向其两个子节点连一条边权为 $0$ 的边。
3. 对于第三类查询的线段树：
   • 原图顶点 $l$ 向对应的叶子节点连一条边权为 $0$ 的边。
   • 每个非叶子节点从其两个子节点连一条边权为 $0$ 的边（方向与第二类相反）。
4. 处理每个第二类查询：从顶点 $v$ 向线段树中所有覆盖 $[l, r)$ 的最大节点连一条边权为 $w$ 的边。
5. 处理每个第三类查询：从线段树中所有覆盖 $[l, r)$ 的最大节点向顶点 $v$ 连一条边权为 $w$ 的边。
6. 在构建好的图上运行 Dijkstra 算法，求出从起点到所有顶点的最短路径。

复杂度分析

• 顶点数：原图 $n$ 个顶点，加上两棵线段树各约 $4n$ 个顶点，总共约 $O(n)$ 个顶点。
• 边数：线段树内部边约 $O(n)$ 条，每个查询添加 $O(\lg n)$ 条边，总边数为 $O(n + q \lg n)$。
• 时间复杂度：Dijkstra 算法使用优先队列，复杂度为 $O((n + q \lg n) \log n)$。

代码说明

• 使用邻接表存储图结构。
• 线段树节点编号从 $n+1$ 开始，避免与原图顶点冲突。
• 对于第二类查询的线段树，递归地将区间 $[l, r)$ 分解为 $O(\lg n)$ 个线段树节点，并从 $v$ 向这些节点连边。
• 对于第三类查询的线段树，同样分解区间，但从这些节点向 $v$ 连边。
• 最后运行 Dijkstra 算法，使用 std::priority_queue 进行堆优化。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#define N 100010
#define M 300110
#define lint long long
#define min(x, y) ((x) < (y) ? (x) : (y))
int n, m, s, cnt, root1, root2;
int head[M], lc[M], rc[M], tot;
struct edge {
	int v, w, nxt; 
}edge[N * 20];
inline void AddEdge(int u, int v, int w) { //在图中添加一条从u连向v的权值为w的单向边
    edge[++tot].v = v, edge[tot].w = w, edge[tot].nxt = head[u]; head[u] = tot; //前向星存边
}
void build1(int &p,int l,int r) { //build关于2操作的线段树
    if (l == r) {
		p = l; //已经是子节点，直接赋值，以便后面加边。
		return;
	}
    p = ++cnt;  //数组模拟链表
    int mid = (l + r) >> 1;
    build1(lc[p], l, mid);
    build1(rc[p], mid + 1, r);
    AddEdge(p, lc[p], 0); //从p向p的左右子树添加一条权值为0的有向边
	AddEdge(p, rc[p], 0); //上图的左边一半的灰色边就是这个build创建的
}
void build2(int &p, int l, int r) { //build关于3操作的线段树
    if (l == r) { 
		p = l; 
		return;
	}
    p = ++cnt;
    int mid = (l + r) >> 1;
    build2(lc[p], l, mid);
    build2(rc[p], mid + 1, r);
    AddEdge(lc[p], p, 0); //从p的左右子树向p添加一条权值为0的有向边
	AddEdge(rc[p], p, 0); //右边一半的灰色边就是这个build创建的
}
int L, R;
void updata(int p, int l, int r, int u, int w, int type) {
    if(L <= l && r <= R) { //完全涵盖直接根据type加边
        type == 2 ? AddEdge(u, p, w) : AddEdge(p, u, w);
        return;
    }
    int mid = (l + r) >> 1;
    if (L <= mid) updata(lc[p], l, mid, u, w, type);
    if (mid < R) updata(rc[p], mid + 1, r, u, w, type);
}
const lint INF = 0x3F3F3F3F3F3F3F3F;
lint dist[M];
std::queue<int> Q;
void SPFA(int s) {  //最短路部分
    memset(dist, 0x3F, sizeof dist);
    dist[s] = 0; Q.push(s);
    while(!Q.empty()) {
        int u = Q.front(); Q.pop();
        for(int i = head[u]; i; i = edge[i].nxt) {
            int v = edge[i].v, w = edge[i].w;
            if (dist[u] + w < dist[v]) 
				dist[v] = dist[u] + w,
				Q.push(v);
        }
    }
}
int main() {
	scanf("%d%d%d", &n, &m, &s);
    cnt = n; //由于建边要求，线段树的结点从n+1开始编号
    build1(root1, 1, n); 
	build2(root2, 1, n);
    while (m--) {
        int opt, u, v, w;
		scanf("%d", &opt);
        if(opt == 1) {
			scanf("%d%d%d", &u, &v, &w);
            AddEdge(u, v, w); //由于上面对叶子结点的处理，这里可以直接加边
        }
        else {
			scanf("%d%d%d%d", &u, &L, &R, &w);
        	updata(opt == 2 ? root1 : root2, 1, n, u, w, opt);
        }
    }
    SPFA(s);
    for(int i = 1; i <= n; i++) 
		std::cout << (dist[i] < INF ? dist[i] : -1) << " ";
    return 0;
}