先开坑,有时间再说。
例题
CF786B Legacy
Code
//线段树优化建图,从寒假一直咕到暑假
//之前觉得难得不行,现在看还是挺好理解的
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN = 2e6 + 10;
int n, m, s, cnt, root_in, root_out;
int head[MAXN];
long long dis[MAXN];
bool used[MAXN];
queue<int> q;
struct Edge{
int to, next;
long long dis;
}e[MAXN];
inline void Add(int u, int v, long long w){
e[++cnt].to = v;
e[cnt].dis = w;
e[cnt].next = head[u];
head[u] = cnt;
}
struct Segment_Tree{
int tot;
struct Tree{
int lson, rson;
}tr[MAXN];
#define lson(x) tr[x].lson
#define rson(x) tr[x].rson
void Build_out(int &rt, int l, int r){
if(l == r){
rt = l;
return;
}
rt = ++tot;
int mid = (l + r) >> 1;
Build_out(lson(rt), l, mid);
Build_out(rson(rt), mid + 1, r);
Add(rt, lson(rt), 0);
Add(rt, rson(rt), 0);
}
void Build_in(int &rt, int l, int r){
if(l == r){
rt = l;
return;
}
rt = ++tot;
int mid = (l + r) >> 1;
Build_in(lson(rt), l, mid);
Build_in(rson(rt), mid + 1, r);
Add(lson(rt), rt, 0);
Add(rson(rt), rt, 0);
}
void Update_out(int rt, int l, int r, int L, int R, int u, int w){
if(L >= l && R <= r){
Add(u, rt, w);
return;
}
int mid = (L + R) >> 1;
if(l <= mid) Update_out(lson(rt), l, r, L, mid, u, w);
if(r > mid) Update_out(rson(rt), l, r, mid + 1, R , u, w);
}
void Update_in(int rt, int l, int r, int L, int R, int v, int w){
if(L >= l && R <= r){
Add(rt, v, w);
return;
}
int mid = (L + R) >> 1;
if(l <= mid) Update_in(lson(rt), l, r, L, mid, v, w);
if(r > mid) Update_in(rson(rt), l, r, mid + 1, R, v, w);
}
}S;
void Spfa(int x){
memset(used, 0, sizeof(used));
memset(dis, 0x3f, sizeof(dis));
dis[x] = 0;
q.push(x);
used[x] = true;
while(!q.empty()){
int k = q.front();
q.pop();
used[k] = false;
for(register int i = head[k]; i; i = e[i].next){
int v = e[i].to;
if(dis[v] > dis[k] + e[i].dis){
dis[v] = 1LL * dis[k] + e[i].dis;
if(!used[v]){
q.push(v);
used[v] = true;
}
}
}
}
}
inline long long read(){
long long x = 0, f = 1;
char c = getchar();
while(c < '0' || c > '9'){
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9'){
x = (x << 1) + (x << 3) + (c ^ 48);
c = getchar();
}
return x * f;
}
int main(){
n = read(), m = read(), s = read();
S.tot = n;
S.Build_out(root_out, 1, n);
S.Build_in(root_in, 1, n);
for(register int i = 1; i <= m; i++){
int opt;
opt = read();
if(opt == 1){
int u, v, w;
u = read(), v = read(), w = read();
Add(u, v, w);
}
else if(opt == 2){
int u, l, r, w;
u = read(), l = read(), r = read(), w = read();
S.Update_out(root_out, l, r, 1, n, u, w);
}
else{
int v, l, r, w;
v = read(), l = read(), r = read(), w = read();
S.Update_in(root_in, l, r, 1, n, v, w);
}
}
Spfa(s);
for(register int i = 1; i <= n; i++){
if(dis[i] == 4557430888798830399) printf("-1 ");
else printf("%lld ", dis[i]);
}
return 0;
}
标签:rt,int,线段,mid,笔记,建图,long,rson,dis
From: https://www.cnblogs.com/TSTYFST/p/16586525.html