网站开发工程师培训机构,wordpress 中文 插件,网站资讯如何做,开广告公司需要学什么技术不是哥们线段树啥都掺和，就连图论也不放过啊！
线段树优化建图
首先，我们先来看一下经典的类型：点 \(u\) 向区间 \([l, r]\) 内的所有点分别连一条边（无向有向随便）。
区间 \([l, r]\) 内的所有点都向点 \(u\) 连…
不是哥们线段树啥都掺和，就连图论也不放过啊！
线段树优化建图
首先，我们先来看一下经典的类型：点 \(u\) 向区间 \([l, r]\) 内的所有点分别连一条边（无向有向随便）。
区间 \([l, r]\) 内的所有点都向点 \(u\) 连一条边。
区间 \([l, r]\) 内的所有点分别向区间 \([L, R]\) 内的所有点连边。对于这三种操作如果暴力建图如果是毒瘤题非常的喜欢卡空间。这时候就需要线段树优化建图了。
对于线段树我们分成两颗。一颗入树，一颗出树。
入树内是父节点连向子节点（从上往下连），出树是子节点连向父节点（从下往上）。
而入树与出树的叶子结点也要相连，这些的边权都是 \(0\)，显然，入树和出树的连边反过来即可。
一般搭配 01BFS 与 dijkstra 使用，还可以有树剖。
那来一道简单的题吧。
例题：Legacy
这里只有三种操作。点连点（\(O(1)\)就行）
点连区间
区间连点处理完操作，建完图后跑一遍 dij 就行了。戳我看代码喵~
vectorpii g[N 3];int tot, rt_in, rt_out, ls[N 3], rs[N 3];
int pos_in[N], pos_out[N];void build_in(int p, int l, int r) { //建权值线段树if (!p) p = ++tot;if (l == r) return pos_in[l] = p, void(); //映射int mid = l + r 1;build_in(ls[p], l, mid), build_in(rs[p], mid + 1, r), g[p].push_back({ls[p], 0}), g[p].push_back({rs[p], 0}); //连边
}void build_out(int p, int l, int r) {if (!p) p = ++tot;if (l == r) return pos_out[l] = p, void();int mid = l + r 1;build_out(ls[p], l, mid), build_out(rs[p], mid + 1, r), g[ls[p]].push_back({p, 0}), g[rs[p]].push_back({p, 0}); //和上面是反着的
}void update_in(int p, int l, int r, int L, int R, int u, int w) {if (L = l r = R) return g[pos_out[u]].push_back({p, w}), void();int mid = l + r 1;if (L = mid) update_in(ls[p], l, mid, L, R, u, w);if (R mid) update_in(rs[p], mid + 1, r, L, R, u, w);
}void update_out(int p, int l, int r, int L, int R, int v, int w) {if (L = l r = R) return g[p].push_back({pos_in[v], w}), void();int mid = l + r 1;if (L = mid) update_out(ls[p], l, mid, L, R, v, w);if (R mid) update_out(rs[p], mid + 1, r, L, R, v, w);
}const int INF = 0x3f3f3f3f3f3f3f3f;int dis[N 3];
bool vis[N 3];void dijstra(int s) { //简单的 dijfor (int i = 1; i = tot; i++) dis[i] = INF, vis[i] = 0;priority_queuepii, vectorpii, greaterpii q;dis[pos_in[s]] = 0, q.push({0, pos_in[s]});while (!q.empty()) {int u = q.top().second; q.pop();if (vis[u]) continue;vis[u] = 1;for (auto X : g[u]) {int v = X.first, w = X.second;if (dis[u] + w dis[v]) dis[v] = dis[u] + w, q.push({dis[v], v});}}
}void build(int n) { //初始化build_in(rt_in, 1, n), build_out(rt_out, 1, n);for (int i = 1; i = n; i++) g[pos_in[i]].push_back({pos_out[i], 0}), g[pos_out[i]].push_back({pos_in[i], 0}); //叶子结点相连
}signed main() {int n = re, q = re, s = re;build(n);while (q--) {int op = re, v = re;if (op == 1) {int u = re, w = re;g[pos_out[v]].push_back({pos_in[u], w});}else if (op == 2) {int l = re, r = re, w = re;update_in(rt_in, 1, n, l, r, v, w);}else {int l = re, r = re, w = re;update_out(rt_out, 1, n, l, r, v, w);}}dijstra(s);for (int i = 1; i = n; i++) wr(dis[pos_in[i]] == INF ? -1 : dis[pos_in[i]]), sp;
} 网站开发工程师培训机构wordpress 中文 插件
网站开发工程师培训机构,wordpress 中文 插件,网站资讯如何做,开广告公司需要学什么技术不是哥们线段树啥都掺和，就连图论也不放过啊！
线段树优化建图
首先，我们先来看一下经典的类型：点 \(u\) 向区间 \([l, r]\) 内的所有点分别连一条边（无向有向随便）。
区间 \([l, r]\) 内的所有点都向点 \(u\) 连…
不是哥们线段树啥都掺和，就连图论也不放过啊！
线段树优化建图
首先，我们先来看一下经典的类型：点 \(u\) 向区间 \([l, r]\) 内的所有点分别连一条边（无向有向随便）。
区间 \([l, r]\) 内的所有点都向点 \(u\) 连一条边。
区间 \([l, r]\) 内的所有点分别向区间 \([L, R]\) 内的所有点连边。对于这三种操作如果暴力建图如果是毒瘤题非常的喜欢卡空间。这时候就需要线段树优化建图了。
对于线段树我们分成两颗。一颗入树，一颗出树。
入树内是父节点连向子节点（从上往下连），出树是子节点连向父节点（从下往上）。
而入树与出树的叶子结点也要相连，这些的边权都是 \(0\)，显然，入树和出树的连边反过来即可。
一般搭配 01BFS 与 dijkstra 使用，还可以有树剖。
那来一道简单的题吧。
例题：Legacy
这里只有三种操作。点连点（\(O(1)\)就行）
点连区间
区间连点处理完操作，建完图后跑一遍 dij 就行了。戳我看代码喵~
vectorpii g[N 3];int tot, rt_in, rt_out, ls[N 3], rs[N 3];
int pos_in[N], pos_out[N];void build_in(int p, int l, int r) { //建权值线段树if (!p) p = ++tot;if (l == r) return pos_in[l] = p, void(); //映射int mid = l + r 1;build_in(ls[p], l, mid), build_in(rs[p], mid + 1, r), g[p].push_back({ls[p], 0}), g[p].push_back({rs[p], 0}); //连边
}void build_out(int p, int l, int r) {if (!p) p = ++tot;if (l == r) return pos_out[l] = p, void();int mid = l + r 1;build_out(ls[p], l, mid), build_out(rs[p], mid + 1, r), g[ls[p]].push_back({p, 0}), g[rs[p]].push_back({p, 0}); //和上面是反着的
}void update_in(int p, int l, int r, int L, int R, int u, int w) {if (L = l r = R) return g[pos_out[u]].push_back({p, w}), void();int mid = l + r 1;if (L = mid) update_in(ls[p], l, mid, L, R, u, w);if (R mid) update_in(rs[p], mid + 1, r, L, R, u, w);
}void update_out(int p, int l, int r, int L, int R, int v, int w) {if (L = l r = R) return g[p].push_back({pos_in[v], w}), void();int mid = l + r 1;if (L = mid) update_out(ls[p], l, mid, L, R, v, w);if (R mid) update_out(rs[p], mid + 1, r, L, R, v, w);
}const int INF = 0x3f3f3f3f3f3f3f3f;int dis[N 3];
bool vis[N 3];void dijstra(int s) { //简单的 dijfor (int i = 1; i = tot; i++) dis[i] = INF, vis[i] = 0;priority_queuepii, vectorpii, greaterpii q;dis[pos_in[s]] = 0, q.push({0, pos_in[s]});while (!q.empty()) {int u = q.top().second; q.pop();if (vis[u]) continue;vis[u] = 1;for (auto X : g[u]) {int v = X.first, w = X.second;if (dis[u] + w dis[v]) dis[v] = dis[u] + w, q.push({dis[v], v});}}
}void build(int n) { //初始化build_in(rt_in, 1, n), build_out(rt_out, 1, n);for (int i = 1; i = n; i++) g[pos_in[i]].push_back({pos_out[i], 0}), g[pos_out[i]].push_back({pos_in[i], 0}); //叶子结点相连
}signed main() {int n = re, q = re, s = re;build(n);while (q--) {int op = re, v = re;if (op == 1) {int u = re, w = re;g[pos_out[v]].push_back({pos_in[u], w});}else if (op == 2) {int l = re, r = re, w = re;update_in(rt_in, 1, n, l, r, v, w);}else {int l = re, r = re, w = re;update_out(rt_out, 1, n, l, r, v, w);}}dijstra(s);for (int i = 1; i = n; i++) wr(dis[pos_in[i]] == INF ? -1 : dis[pos_in[i]]), sp;
}