CF786B Legacy

发表于 | 阅读数
  • 开启一扇从星球 $v$ 到星球 $u$ 的传送门；
  • 这传送门可以从一个星球出发通往多个星球
  • 这传送门可以从多个星球出发到达同一个星球

“线段树优化建图“就是把区间放到线段树里做，点会增加到$nlog_n$。

但是连边就少。

考虑传送门$2$:可以直接把$u$连向区间$[l,r]$的$log_n$个小区间

考虑传送门$3$:如果一颗线段树那么显然不能$[l,r]\rightarrow u$,因为$[l,r]\rightarrow son$儿子的。儿子无法

考虑再建一个线段树$[l,r]_2\leftarrow son_2$,则第一个线段树就是$[l,r]_1\rightarrow son_1$

$u\rightarrow[l,r]\rightarrow v$

等价与

$son[u]_2\rightarrow[l,r]_2\rightarrow son[v]_1\rightarrow son[v]_2$

注意到$son[v]_2与son[v]_1$是连同的。

归纳来说就是一个出树，一个入树。

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<ll, int>
#define mk make_pair
const int N = 1e5 + 10;
const int mod = 1e9 + 7;
int read()
{
int 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 - '0', c = getchar();
return x \* f;
}
const int SN = 4e6 + 10;
struct Segment
{
vector<pii> g[SN];
int id[N], vis[SN], out[SN], in[SN];
int scnt;
ll dis[SN];
void init(int pos, int l, int r, int fa)
{
out[pos] = ++scnt;
in[pos] = ++scnt;
if (fa != -1)
g[out[pos]].push_back(mk(out[fa], 0)), g[in[fa]].push_back(mk(in[pos], 0));
if (l == r)
{

            id[l] = pos;
            g[out[pos]].push_back(mk(in[pos], 0)), g[in[pos]].push_back(mk(out[pos], 0));

            return;
        }

        int mid = (l + r) >> 1;
        init(pos << 1, l, mid, pos);
        init(pos << 1 | 1, mid + 1, r, pos);
    }
    void add(int ql, int qr, int pos, int l, int r, int op, int x, int w)
    {
        if (ql <= l && r <= qr)
        {
            if (op == 1)
                g[out[id[x]]].push_back(mk(in[pos], w));
            else
            {

                g[out[pos]].push_back(mk(in[id[x]], w));
            }

            return;
        }
        int mid = (l + r) >> 1;
        if (ql <= mid)
            add(ql, qr, pos << 1, l, mid, op, x, w);
        if (qr > mid)
            add(ql, qr, pos << 1 | 1, mid + 1, r, op, x, w);
    }
    void djs(int s, int n)
    {

        priority_queue<pii> q;
        for (int i = 0; i <= n; i++)
            dis[i] = 1e18;
        dis[s] = 0;
        q.push(mk(0, s));
        while (!q.empty())
        {
            int x = q.top().second;
            q.pop();
            if (vis[x])
                continue;
            vis[x] = 1;
            for (pii now : g[x])
            {
                int to = now.first;
                if (dis[to] > dis[x] + now.second)
                {
                    dis[to] = dis[x] + now.second;
                    q.push(mk(-dis[to], to));
                }
            }
        }
    }
    ll d(int x)
    {
        return dis[in[id[x]]];
    }

} T;

int main()
{
int n = read(), m = read(), s = read();
T.init(1, 1, n, -1);
for (int i = 1; i <= m; i++)
{
int op = read(), v = read();
if (op == 1)
{
int u = read(), w = read();
T.g[T.out[T.id[v]]].push_back(mk(T.in[T.id[u]], w));
}
else
{
int l = read(), r = read(), w = read();
T.add(l, r, 1, 1, n, op == 2, v, w);
}
}

    T.djs(T.out[T.id[s]], T.scnt);

    for (int i = 1; i <= n; i++)
        printf("%lld ", T.d(i) == 1e18 ? -1 : T.d(i));

}