直接看题吧，思路有了，但是有些题代码没打。兔子正在加油中。
优化建图
I.（线段树）CF786B Legacy
题目描述三种连边操作，执行 \(q(1\le n\le10^5)\) 次：
- \(x\xrightarrow{w}y\)
- \(x\xrightarrow{w}y,y\in[l,r]\)
- \(x\xrightarrow{w}y,x\in[l,r]\)
求 \(s\) 到其余点的最短路。
暴力连边肯定不行。
有没有什么东西是把一个区间拆分成 \(\log\) 个的？
当然是线段树优化建图啦。因为加入的是一个区间，所以用线段树上的 \(\log\) 个结点来表示区间，对这些结点连边。
对于 \([l,r] \to v\)，把 \(\log\) 个结点连向线段树上的 \(v\)，之后把线段树本身连成一颗内向树。
对于 \([l,r] \gets v\)，在对线段树内部连边时，显然不能和上一种情况连同一些结点，不然最短路都是 \(0\)。于是重新开一颗线段树，把这个颗树连成外向树。对于这颗线段树上的 \(\log\) 个结点，连向上内向树上的 \(v\)。
这两颗树上的叶子在原图上是同一个点，所以这两颗树的叶子要连权值为 \(0\) 的边（显然只需要外向树向内向树连边）。
对于建出来的图跑最短路，有 \(n\) 个结点 \(m\log n\) 条边，堆优化 Dijkstra 时间复杂度 \(\mathcal{O}(m\log_2 n)\)。
CF786B[code]#include#define int long long#define endl '\n'#define pi pairusing namespace std;const int N=3e6+10,K=5e5;int n, m, s, op, a[N], d[N];bool vis[N];priority_queue q;int pre[N], cnt;struct node{ int to, next, l;}g[N];void add(int u,int v,int l){ g[++cnt] = {v, pre, l}; pre = cnt; return ;}struct Segment_Tree{#define ls (k > 1; add(k, ls, 0); add(k, rs, 0); add(ls + K, k + K, 0); add(rs + K, k + K, 0); build(ls, l, mid); build(rs, mid+1, r); } void modify(int k, int l, int r, int lx, int rx, int v, int w){ if(l >= lx && r > 1; if(lx mid) modify(rs, mid+1, r, lx, rx, v, w); return ; }}tree;inline void dijkstra(int s){ memset(d, 0x3f, sizeof d); d = 0; q.push(make_pair(0, s)); while(q.size()){ int x = q.top().second; q.pop(); if(vis[x]) continue; vis[x] = true; for(int i = pre[x]; i; i = g.next){ int to = g.to, l = g.l; if(d[to] > d[x] + l) { d[to] = d[x] + l; q.push(make_pair(-d[to], to)); } } } return ;}inline int read(){ int x; cin >> x; return x;}signed main(){ cin.tie(nullptr)->sync_with_stdio(false); n = read(), m = read(), s = read(); tree.build(1, 1, n); for(int i = 1; i |
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
千斤顶
照妖镜
