线段树优化建图(cf787d, 2019Wannafly Winter Camp Day7 Div1 E)

线段树优化建图,用于区间到区间建边时降低空间复杂度 建立两颗线段树,一颗in, 代表进入这个区间,一颗out,代表从这个区间出去 in树从父亲向儿子建边,代表宏观进入整个区间,不向下寻找 out树从儿子向父亲建边,代表出去 in树向out树对应点建边,代表从这个点进去可以从它出去 建真正的边时: 1: 单点向单点: out树对应点向in树对应点建边 2: 单点向区间: out树对应点向in树对应区间建边 3: 区间向单点: out树对应区间向in树对应点建边 4: 区间向区间: out树区间对新点P建边,P向in树对应点建边

cf787D 最短路裸题

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
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
using LL = long long;
vector<pair<int,int>> G[N << 3];
int in[N << 2], out[N << 2], pos[N], n, q, s, t, v, u, l, r, w, tot;
LL dis[N << 3];

inline void add(int x, int y, int v) {
G[x].push_back(make_pair(y, v));
}

void build_in(int rt, int l, int r) {
if(l == r) {
pos[l] = rt;
return;
}
int mid = l + r >> 1;
build_in(rt << 1, l, mid);
build_in(rt << 1 | 1, mid + 1, r);
add(rt, rt << 1, 0); //in树父亲向儿子建边
add(rt, rt << 1 | 1, 0);
}

void build_out(int rt, int l, int r) {
add(rt, tot + rt, 0); //in树向out树建边
if(l == r) {
return;
}
int mid = l + r >> 1;
build_out(rt << 1, l, mid);
build_out(rt << 1 | 1, mid + 1, r);
add(tot + (rt << 1), tot + rt, 0); //out树儿子向父亲建边
add(tot + (rt << 1 | 1), tot + rt, 0);
}

void update_in(int rt, int l, int r, int L, int R, int from, int val) {
if(L <= l && r <= R) {
add(tot + pos[from], rt, val);
return;
}
int mid = l + r >> 1;
if(L <= mid)
update_in(rt << 1, l, mid, L, R, from, val);
if(mid < R)
update_in(rt << 1 | 1, mid + 1, r, L, R, from, val);
}

void update_out(int rt, int l, int r, int L, int R, int pnt, int val) {
if(L <= l && r <= R) {
add(tot + rt, pos[pnt], val);
return;
}
int mid = l + r >> 1;
if(L <= mid)
update_out(rt << 1, l, mid, L, R, pnt, val);
if(mid < R)
update_out(rt << 1 | 1, mid + 1, r, L, R, pnt, val);
}

struct node {
LL dis;
int id;
bool operator<(const node &rhs) const {
return dis > rhs.dis;
}
};

void dijk() {
memset(dis, 0x3f, sizeof(dis));
dis[pos[s]] = 0;
priority_queue<node> pq;
pq.push({0, pos[s]});
while(!pq.empty()) {
node u = pq.top();
pq.pop();
if(dis[u.id] < u.dis) continue;
for(auto &j: G[u.id]) {
if(dis[j.first] > u.dis + j.second) {
dis[j.first] = u.dis + j.second;
pq.push({dis[j.first], j.first});
}
}
}
}

int main() {
scanf("%d%d%d", &n, &q, &s);
tot = n << 2;
build_in(1, 1, n);
build_out(1, 1, n);
while(q--) {
scanf("%d", &t);
if(t == 1) { //v->u
scanf("%d%d%d", &v, &u, &w);
add(pos[v] + tot, pos[u], w);
}
if(t == 2) { //v->[l,r]
scanf("%d%d%d%d", &v, &l, &r, &w);
update_in(1, 1, n, l, r, v, w);
}
if(t == 3) { //[l,r]->v
scanf("%d%d%d%d", &v, &l, &r, &w);
update_out(1, 1, n, l, r, v, w);
}
}
dijk();
for(int i = 1; i <= n; ++i) {
printf("%lld%c", dis[pos[i]] == 0x3f3f3f3f3f3f3f3f ? -1 : dis[pos[i]], " \n"[i == n]);
}

return 0;
}

2019Wannafly Winter Camp Day7 Div1 E 给你线性探查法哈希后的序列,求字典序最小的原序列 记一个数应该在的位置为\(pos\), 实际在的位置为\(s\),那么\(pos\)\(s-1\)(模\(n\)意义下的)这些位置的数肯定在\(s\)前被插入 建边拓扑排序就行了,要求字典序最小就用优先队列,只有区间向单点建边只要out那颗树就行了

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
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;

vector<int> G[N << 2], ans;
int deg[N << 2], pos[N], id[N << 2], a[N], n;

void add(int x, int y) {
G[x].push_back(y);
++deg[y];
}

void build(int rt, int l, int r) {
id[rt] = -1;
if(l == r) {
pos[l] = rt;
id[rt] = l;
return;
}
int mid = l + r >> 1;
add(rt << 1, rt);
add(rt << 1 | 1, rt);
build(rt << 1, l, mid);
build(rt << 1 | 1, mid + 1, r);
}

void Add(int rt, int l, int r, int L, int R, int pnt) {
if(L <= l && r <= R) {
add(rt, pos[pnt]);
return;
}
int mid = l + r >> 1;
if(L <= mid)
Add(rt << 1, l, mid, L, R, pnt);
if(mid < R)
Add(rt << 1 | 1, mid + 1, r, L, R, pnt);
}

void topo() {
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
for(int i = 0; i < n; ++i)
if(!deg[pos[i]])
pq.push(make_pair(a[i], pos[i]));
while(!pq.empty()) {
pair<int, int> u = pq.top();
pq.pop();
if(u.first != -1)
ans.push_back(u.first);
for(auto &it: G[u.second])
if(--deg[it] == 0)
pq.push(make_pair(~id[it] ? a[id[it]] : -1, it));
}
for(int i = 0; i < ans.size(); ++i) {
printf("%d%c", ans[i], " \n"[i == ans.size() - 1]);
}
}

int main() {
scanf("%d", &n);
build(1, 0, n - 1);
for(int i = 0; i < n; ++i) {
scanf("%d", &a[i]);
int tmp = a[i] % n;
if(tmp == i) continue;
if(tmp < i)
Add(1, 0, n - 1, tmp, i - 1, i);
else {
Add(1, 0, n - 1, tmp, n - 1, i);
if(i)
Add(1, 0, n - 1, 0, i - 1, i);
}
}
topo();
return 0;
}