CF786B Legacy

大致题意：给一个图，有3种边，t=1时，是点u对点v的单向边，t=2时，是点u到标号为[l,r]的点的单向边，t=3时，是标号为[l,r]到点u的边，求单源多汇最短路。

注意，点的数量为10^5，所以如果把每个点之间的边都存下来会占用GB级别的内存，显然这不是出题者所希望看到的，我们应该对存储边的方式进行调整。

既然我们不能把每个点对点的边都存下来，不如新建一些集散点用进行集中和分散，就像现实生活中的货运集散点一样，这样的话边的数量就会有所减少。

再观察题目给出边的特点，它虽然给出的边是一个点指向多个点的边，但是这些点的边都标号都是连续的。所以把标号相邻的点联向一个共同的集散点，然后将二者共同的边改为从这个集散点联向其他点，这样将会稳定且有效地减少边的数量。

但是对于新图，边数仍然不少，但我们仍然可以对新建的点重复上述步骤来增加集散点，直到所有点都联向了一个集散点。

注意，入边和出边的集散点应该分开来建。

在纸上模拟上述步骤，会发现这不就是两颗线段树吗？对，它的确和线段树相差无几。所以我们可以用线段树的建树函数和更新过程来进行构建新图。之于最短路就不是本题的主要问题了。

#include <bits/stdc++.h>
#define maxn 1700000
#define ll long long
#define mp make_pair
#define pb push_back
#define st first
#define ed second
using namespace std;
inline void read(int &x) {
    char ch;
    bool flag = false;
    for (ch = getchar(); !isdigit(ch); ch = getchar())if (ch == '-') flag = true;
    for (x = 0; isdigit(ch); x = x * 10 + ch - '0', ch = getchar());
    x = flag ? -x : x;
}
inline void write(int x) {
    static const int maxlen = 100;
    static char s[maxlen];
    if (x < 0) {   putchar('-'); x = -x;}
    if (!x) { putchar('0'); return; }
    int len = 0; for (; x; x /= 10) s[len++] = x % 10 + '0';
    for (int i = len - 1; i >= 0; --i) putchar(s[i]);
}


set< pair<ll, int> > s;
vector < pair<int, int> > v[maxn];

int n, m, st;
ll dist[maxn];
int num[maxn][2], tot;
//x=0代表入点，x=1代表出点
int build(int p, int l, int r, int x) {
    if (l == r)
        return num[p][x] = l;
    num[p][x] = ++tot;
    int mid = (l + r) / 2;
    int ls = build(p * 2, l, mid, x);
    int rs = build(p * 2 + 1, mid + 1, r, x);
    if (x == 0)
    {
        v[num[p][x]].push_back(mp(ls, 0));
        v[num[p][x]].push_back(mp(rs, 0));
    }
    else
    {
        v[ls].push_back(mp(num[p][x], 0));
        v[rs].push_back(mp(num[p][x], 0));
    }
    return num[p][x];
}


void update(int p, int l, int r, int a, int b, int x, int y, int op) {
    if ((l == a) && (r == b))
    {
        if (op == 0)
            v[x].push_back(mp(num[p][op], y));
        else
            v[num[p][op]].push_back(mp(x, y));
        return ;
    }
    int mid = (l + r) / 2;
    if (b <= mid)
        update(p * 2, l, mid, a, b, x, y, op);
    else if (a > mid)
        update(p * 2 + 1, mid + 1, r, a, b, x, y, op);
    else
    {
        update(p * 2, l, mid, a, mid, x, y, op);
        update(p * 2 + 1, mid + 1, r, mid + 1, b, x, y, op);
    }
}




int main() {
    memset(dist, -1, sizeof(dist));
    read(n); read(m); read(st);
    tot = n;
    build(1, 1, n, 0);
    build(1, 1, n, 1);
    for (int i = 1; i <= m; i++)
    {
        int t;
        read(t);
        if (t == 1)
        {
            int a, b, c;
            read(a); read(b); read(c);
            v[a].pb(make_pair(b, c));
        }
        else
        {
            int v, l, r, w;
            scanf("%d%d%d%d", &v, &l, &r, &w);
            update(1, 1, n, l, r, v, w, t - 2);
        }
    }
    s.insert(mp(0, st));
    while (!s.empty())
    {
        ll y = s.begin()->st, x = s.begin()->ed;
        s.erase(s.begin());
        if (dist[x] != -1)
            continue;
        dist[x] = y;
        for (int i = 0; i < v[x].size(); i++)
            if (dist[v[x][i].st] == -1)
                s.insert(mp(1ll * v[x][i].ed + dist[x], v[x][i].st));
    }
    for (int i = 1; i <= n; i++)
        printf("%I64d ", dist[i]);
    return 0;
}