今天写了道线段树优化建图的板子题，感觉学算法的还是要记录下来，将来方便复习也算是对竞赛生涯的一种回忆
http://codeforces.com/problemset/problem/786/B，洛谷评级还是省选，如果是比赛现场想出来确实厉害，但是现在嘛，已经是时代眼泪了
归纳下特点：和区间有关的图论问题
直接上代码讲解：
我主要是采取了动态开点线段树与dijkstra最段路算法
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
#define int long long
int read(){
int f = 1, x = 0;
char ch = getchar();
while(ch < '0' || ch > '9'){
if(ch == '-') f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9'){
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
return f * x;
}//这是一个常见的快读模板，有点是作为int返回类型可以实现类似python的操作（没怎么学过，大概），缺点是面对以持续读入为条件不合适
const int N = 3e5 + 3;//2棵线段树尾部相连，叶子数为1e5的图形大概有3e5 - 2个点，联想双端广搜的图
struct semgtr{
int lc, rc;
#define lc(x) tr[x].lc//lc即left child，rc同理
#define rc(x) tr[x].rc//记录一个小知识，define运算的话最好打括号，因为只是关键字的替换所以运算顺序你懂的，养成写成函数的习惯也不错
}tr[20 * N];//理论上点数N就行，但是实际RE洛谷老哥建议开大点，空间足，确实这种数据结构优化的题空间会给的很足我就都开20 * N了
int idx, h[3 * N], e[20 * N], ne[20 * N], w[20 * N], tot, inr, outr, d[N * 3];//关于边数，我虽然说了可以开大点，但是为了确保下限我还是算了下，众所周知，线段树最多会把查询的区间划分成loglen，然后这题n，q范围又一样，所以边数大概是qlogN，然后log不会超过20,所以直接设的20,总之空间够你就开大点
void add(int a, int b,int c){
e[idx] = b;
ne[idx] = h[a];
w[idx] = c;
h[a] = idx++;
}//平平无奇邻接表，之前看过一本书说写成结构体会更优，但是吧。个人认为小区别，按习惯吧
void build(int &p, int l, int r, bool op){//op是表示在建入树还是出树，虽然这里画图会好理解，但是我一直是脑测玩家，相信未来的我能模拟出图，你就想象一个点要去你已经建好的菱形（2棵二叉树拼成）里了，入树就是你顺着箭头去到一个节点，然后这个节点的去路是它的子节点，否则，就是它的子节点能顺着箭头走到你，即出树
if(l == r){
p = l;
return;
}
p = ++tot;//这就是动态开点，按下面的build无论是lc还是rc走到这都是0，如果你不会动态开点（很好学）或者懒得学直接普通线段树堆式存储也行，看一个同学就是这样写的
int mid = (l + r) >> 1;
build(lc(p), l, mid, op);
build(rc(p), mid + 1, r, op);
if(!op){
add(lc(p), p, 0);
add(rc(p), p, 0);
}
else{
add(p, lc(p), 0);
add(p, rc(p), 0);
}
}
void modify(int &p, int l, int r, int L, int R, int u, int k, bool flag){//同样的，用flag标记是往哪棵树建边，其实还有一个办法你像并查集的扩展域一样加一个大常数来区分，前面 * flag也行
if(L <= l && r <= R){
flag ? add(u, p, k) : add(p, u, k);
return;
}
int mid = (l + r) >> 1;
if(L <= mid) modify(lc(p), l, mid, L, R, u, k, flag);
if(R > mid) modify(rc(p), mid + 1, r, L, R, u, k, flag);
}
bool vis[N * 3];//也是开大了感觉
void dijstra(int s){
memset(d, 0x3f3f3f, sizeof d);//初值能大别小
d[s] = 0;
priority_queue<pair<int, int> > q;
q.push({0, s});
while(!q.empty()){
int u = q.top().second;
q.pop();
if(vis[u]) continue;
vis[u] = true;
for(int i = h[u]; i != -1; i = ne[i]){
int v = e[i];
if(!vis[v] && d[v] > d[u] + w[i]){
d[v] = d[u] + w[i];
q.push({-d[v], v});
}
}
}
}//板子
signed main(){
memset(h, -1, sizeof h);
int n = read(), m = read(), s = read();
tot = n;//前n个点就是叶子
build(inr, 1, n, 1);
build(outr, 1, n, 0);//分别记一下入树和出树的节点编号
while(m--){
int op = read();
if(op == 1){
int u = read(), v = read();
add(u, v, read());
}
else{
int p = read(), l = read(), r = read(), cost = read();
modify(op == 2 ? inr : outr, 1, n, l, r, p, cost, op == 2);
}
}
dijstra(s);
for(int i = 1; i <= n; i++) printf("%lld ",d[i] != d[0] ? d[i] : -1);//按我的写法从1开始编号d[0]就是不变，同理，和她相同的距离节点就说明到不了，按题目输出-1
return 0;
}
标签：lc,int,线段,add,read,建图,rc,优化,op
From： https://www.cnblogs.com/tingzhimian/p/18351536