传送门
题意
分析
线段树优化建图的板子题
我们把区间映射到线段树的一个一个点上，然后建两颗线段树，第一颗线段树自上向下建边，边权为0，第二颗线段树自下往上建边，边权为0，这样就可以做到两颗线段树内的点互相走通
然后操作2可以在第一个线段树内加边，操作3可以在第二个线段树内加边
代码
#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define debug(x) cout<<#x<<":"<<x<<endl;
#define dl(x) printf("%lld\n",x);
#define di(x) printf("%d\n",x);
#define _CRT_SECURE_NO_WARNINGS
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, int> PII;
typedef vector<int> VI;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int N = 2e6 + 10;
const ll mod = 1000000007;
const double eps = 1e-9;
const double PI = acos(-1);
template<typename T>inline void read(T &a) {char c = getchar(); T x = 0, f = 1; while (!isdigit(c)) {if (c == '-')f = -1; c = getchar();}while (isdigit(c)) {x = (x << 1) + (x << 3) + c - '0'; c = getchar();} a = f * x;
}
int gcd(int a, int b) {return (b > 0) ? gcd(b, a % b) : a;}
int tr1[N], tr2[N], cnt;
int h[N], e[N], ne[N], w[N], idx;
int n, m, s;
ll d[N];
bool st[N];void add(int x, int y, int z) {ne[idx] = h[x], e[idx] = y, w[idx] = z, h[x] = idx++;
}int build1(int u, int l, int r) {tr1[u] = ++cnt;if (l == r) {return tr1[u] = l;}int mid = (l + r) >> 1;int lon = build1(u << 1, l, mid);int ron = build1(u << 1 | 1, mid + 1, r);add(tr1[u], lon, 0);add(tr1[u], ron, 0);return tr1[u];
}int build2(int u, int l, int r) {tr2[u] = ++cnt;if (l == r) {return tr2[u] = l;}int mid = (l + r) >> 1;int lon = build2(u << 1, l, mid);int ron = build2(u << 1 | 1, mid + 1, r);add(lon, tr2[u], 0);add(ron, tr2[u], 0);return tr2[u];
}void add1(int u, int l, int r, int L, int R, int x, int val) {if (l >= L && r <= R) {add(x, tr1[u], val);return;}int mid = (l + r) >> 1;if (L <= mid) add1(u << 1, l, mid, L, R, x, val);if (R > mid) add1(u << 1 | 1, mid + 1, r, L, R, x, val);
}void add2(int u, int l, int r, int L, int R, int x, int val) {if (l >= L && r <= R) {add(tr2[u], x, val);return;}int mid = (l + r) >> 1;if (L <= mid) add2(u << 1, l, mid, L, R, x, val);if (R > mid) add2(u << 1 | 1, mid + 1, r, L, R, x, val);
}void dij() {memset(d,0x3f,sizeof d);d[s] = 0;priority_queue<PII, vector<PII>, greater<PII> > Q;Q.push(PII(0, s));while (Q.size()) {PII p = Q.top();Q.pop();int t = p.second;if (st[t]) continue;st[t] = true;for (int i = h[t]; i != -1; i = ne[i]) {int j = e[i];if (d[j] > d[t] + w[i]) {d[j] = d[t] + w[i];Q.push(PII(d[j], j));}}}
}int main() {memset(h, -1, sizeof h);read(n), read(m), read(s);cnt = n;build1(1, 1, n);build2(1, 1, n);while (m--) {int op, x, l, r, w;read(op), read(x), read(l), read(r);if (op == 1) add(x, l, r);else {read(w);if (op == 2) add1(1, 1, n, l, r, x, w);else add2(1, 1, n, l, r, x, w);}}dij();for (int i = 1; i <= n; i++) {if (d[i] == INF) d[i] = -1;printf("%lld ", d[i]);}return 0;
}