求助线段树优化建图

Weight_of_the_Soul @ 2022-07-29 14:50:58

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <utility>
#include <vector>
#include <deque>
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;

const int N = 5e5 + 5;

int read() {
    int x = 0, w = 1;
    char c = getchar();

    while(c < '0' || c > '9') {
        if(c == '-')
            w = -1;

        c = getchar();
    }

    while(c >= '0' && c <= '9') {
        x = x * 10 + (c - '0');
        c = getchar();
    }

    return x * w;
}

struct Tree {
    int l, r;
    int pos;

    #define l1(x) t1[x].l
    #define r1(x) t1[x].r
    #define l2(x) t2[x].l
    #define r2(x) t2[x].r
    #define pos1(x) t1[x].pos
    #define pos2(x) t2[x].pos

}t1[N << 2], t2[N << 2];

int n, m, s;
int cnt;

struct Graph {
    int v, nxt, w;
}e[N << 1];

int lk[N], ltp;
int rt1, rt2;

void ins(int u, int v, int w) {
    e[++ltp] = (Graph) {v, lk[u], w};
    lk[u] = ltp;
}

struct Node {
    int pos, dis;

    bool operator < (const Node &x) const {
        return x.dis < dis;
    }
};

priority_queue <Node> q;

void build(int p, int l, int r) {
    l1(p) = l, l2(p) = l, r1(p) = r, r2(p) = r;
    if(l == r) {
        pos1(p) = l;
        pos2(p) = l;
        return ;
    }

    int mid = (l + r) >> 1;
    rt1 = pos1(p) = ++cnt;
    rt2 = pos2(p) = ++cnt;

    build(p << 1, l, mid);
    ins(pos1(p << 1), pos1(p), 0);
    ins(pos2(p), pos2(p << 1), 0);

    build(p << 1 | 1, mid + 1, r);
    ins(pos1(p << 1 | 1), pos1(p), 0);
    ins(pos2(p), pos2(p << 1 | 1), 0);
}

void change(int p, int l, int r, int x, int opt) {
    if(l <= l1(p) && r1(p) <= r) {
        if(opt) ins(x, p, 0);
        else ins(p, x, 0);
        return ;
    }

    int mid = (l1(p) + r1(p)) >> 1;
    if(l <= mid) change(p << 1, l, r, x, opt);
    if(r > mid) change(p << 1 | 1, l, r, x, opt);
}

int dis[N];

void bfs() {
    memset(dis, 0x3f, sizeof(dis));
    deque <int> q;

    dis[s] = 0;
    q.push_back(s);

    while(!q.empty()) {
        int p = q.front();
        q.pop_front();

        for(int i = lk[p]; i; i = e[i].nxt) {
            int v = e[i].v, w = e[i].w;

            if(dis[v] > dis[p] + w) {
                dis[v] = dis[p] + w;
                if(w) q.push_back(v);
                else q.push_front(v);
            }
        }
    }
}

int main() {
    n = read(), m = read(), s = read();
    cnt = n;

    build(1, 1, n);
    for(int i = 1; i <= m; i++) {
        int a = read(), b = read(), c = read(), d = read(), x = ++cnt, y = ++cnt;
        ins(x, y, 1);
        change(1, a, b, x, 0);
        change(1, c, d, y, 1);
        x = ++cnt, y = ++cnt;
        ins(x, y, 1);
        change(1, c, d, x, 0);
        change(1, a, b, y, 1);
    }

    bfs();

    for(int i = 1; i <= n; i++)
        printf("%d\n", dis[i]);
    return 0;
}

by Weight_of_the_Soul @ 2022-07-29 14:59:27

@L_fire

by _cyle_King @ 2022-07-29 15:05:45

@Napoleon_Bonaparte 您这一棵树好像不行吧。

by Weight_of_the_Soul @ 2022-07-29 15:07:11

@_cyle_King 大佬，我开的不是两棵来着吗（doge

by _cyle_King @ 2022-07-29 15:07:41

@_cyle_King 说错了，不是一棵树，是两棵树用同一个编号，与一棵树没有区别。

by _cyle_King @ 2022-07-29 15:07:55

@Napoleon_Bonaparte

by Weight_of_the_Soul @ 2022-07-29 15:08:19

@_cyle_King 谢谢大佬，我去写写看

by _cyle_King @ 2022-07-29 15:29:02

@Napoleon_Bonaparte 帮您过了，这题空间消耗好大。

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <utility>
#include <vector>
#include <deque>
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
typedef pair<int,int> pr;

const int N = 5e5 + 5;

int read() {
    int x = 0, w = 1;
    char c = getchar();

    while(c < '0' || c > '9') {
        if(c == '-')
            w = -1;

        c = getchar();
    }

    while(c >= '0' && c <= '9') {
        x = x * 10 + (c - '0');
        c = getchar();
    }

    return x * w;
}

struct Tree {
    int l, r;
    int pos;

    #define l1(x) t[x].l
    #define r1(x) t[x].r
    #define l2(x) t[x].l
    #define r2(x) t[x].r

}t[N << 3];
int child[N<<3|1][2];
#define lc(p) child[p][0]
#define rc(p) child[p][1]

int n, m, s;
int cnt;

vector<pr>e[N<<3|1];
int rt1, rt2;

void ins(int u, int v, int w) {
    e[u].emplace_back(v,w);
}

struct Node {
    int pos, dis;

    bool operator < (const Node &x) const {
        return x.dis < dis;
    }
};

priority_queue <Node> q;
int pos[N+1];
void build(int &p, int &q, int l, int r) {
    p=++cnt;q=++cnt;
    l1(p) = l, l2(q) = l, r1(p) = r, r2(q) = r;
    if(l == r) {
        pos[l]=p;
        ins(p,q,0);
        return ;
    }

    int mid = (l + r) >> 1;

    build(lc(p),lc(q),l,mid);
    ins(p,lc(p),0);
    ins(lc(q),q,0);

    build(rc(p),rc(q),mid+1,r);
    ins(p,rc(p),0);
    ins(rc(q),q,0);
}

void change(int p, int l, int r, int x, int opt) {
    if(l <= l1(p) && r1(p) <= r) {
        if(opt) ins(x, p, 0);
        else ins(p, x, 1);
        return ;
    }

    int mid = (l1(p) + r1(p)) >> 1;
    if(l <= mid) change(lc(p), l, r, x, opt);
    if(r > mid) change(rc(p), l, r, x, opt);
}

int dis[N<<3|1];

void bfs() {
    memset(dis, 0x3f, sizeof(dis));
    deque <int> q;

    dis[pos[s]] = 0;
    q.push_back(pos[s]);

    while(!q.empty()) {
        int p = q.front();
        q.pop_front();

        for(auto i:e[p]) {
            int v = i.first, w = i.second;

            if(dis[v] > dis[p] + w) {
                dis[v] = dis[p] + w;
                if(w) q.push_back(v);
                else q.push_front(v);
            }
        }
    }
}

int main() {
    n = read(), m = read(), s = read();
    cnt = n;

    build(rt1,rt2, 1, n);
    for(int i = 1; i <= m; i++) {
        int a = read(), b = read(), c = read(), d = read(), x = ++cnt, y = ++cnt;
        change(rt2, a, b, x, 0);
        change(rt1, c, d, x, 1);
        //ins(x, y, 1);
        change(rt2, c, d, y, 0);
        change(rt1, a, b, y, 1);
    }

    bfs();

    for(int i = 1; i <= n; i++)
        printf("%d\n", dis[pos[i]]);
    return 0;
}

by Weight_of_the_Soul @ 2022-07-29 15:33:53

@_cyle_King 谢谢，我刚才自己过了，感激不尽

by Ptilopsis_w @ 2022-07-29 15:43:17

tql您爆切线段树优化建图

by Meteorshower_Y @ 2022-07-30 06:59:04

orz , 您