题单：https://www.luogu.com.cn/blog/221955/chang-jian-you-hua-jian-tu-ji-qiao

线段树建图优化

dijkstra

题意：n个点，m条边，s是起点，问点s到点1~n的最短距离

有三种边：接下来的 q 行表示 q 种方案。

  • 输入 1 v u w 表示第一种方案，从v向u连边，权值为w
  • 输入 2 v l r w 表示第二种方案，从v向$[l,r]$区间连边，权值为w
  • 输入 3 v l r w 表示第三种方案，从$[l,r]$区间向v连边，权值为w

这里的线段树实际上有两个，分别为u和u+D,左树从上往下，右数从下往上，区间向点连边从右树结点连出，点向区间连入到左树结点。

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
// Problem: B. Legacy
// Contest: Codeforces - Codeforces Round 406 (Div. 1)
// URL: https://codeforces.com/contest/786/problem/B
// Memory Limit: 256 MB
// Time Limit: 2000 ms

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
using ll = long long;

bool multi = 0;

const int N = 1e5 + 10, M = 1e6 + 10, D = 5e5;

int n, m, s;

struct Node{
	int l, r;
}tr[N * 4];
vector<pair<int, int>> g[M];
int dist[M], leaf[M];

inline void build(int u, int l, int r) {
	tr[u] = {l, r};
	if(l == r) {
		leaf[l] = u;
		return;
	}
	int mid = (l + r) / 2;
	g[u].push_back({u << 1, 0});
	g[u].push_back({u << 1 | 1, 0});
	g[(u << 1) + D].push_back({u + D, 0});
	g[(u << 1 | 1) + D].push_back({u + D, 0});
	build(u << 1, l, mid),build(u << 1 | 1, mid + 1, r);
}

inline void connect(int u, int l, int r, int v, int w, int op) {
	if(l <= tr[u].l && tr[u].r <= r) {
		if(op) g[u + D].push_back({v, w});
		else g[v].push_back({u, w});
		return;
	}
	int mid = (tr[u].l + tr[u].r) / 2;
	if(l <= mid) connect(u << 1, l, r, v, w, op);
	if(r > mid) connect(u << 1 | 1, l, r, v, w, op);
}

void dijkstra(){
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> heap;
    heap.push({0, leaf[s]});
    memset(dist, 0x3f, sizeof dist);
    dist[leaf[s]] = 0;
    while(heap.size()){
        auto t=heap.top();
        heap.pop();
        int u = t.second, distance = t.first;
        if(dist[u]<distance) continue;
        for(auto it:g[u]){
            int v=it.first,w=it.second;
            if(dist[v] > dist[u] + w){
                dist[v] = dist[u] + w;
                heap.push({dist[v], v});
            }
        }
    }
}

void solve() {
	cin >> n >> m >> s;
	build(1, 1, n);
	for(int i = 0; i < m; i++) {
		int op;
		cin >> op;
		if(op == 1) {
			int u, v, w;
			cin >> u >> v >> w;
			g[leaf[u]].push_back({leaf[v], w});
		} else {
			int v, l, r, w;
			cin >> v >> l >> r >> w;
			connect(1, l, r, leaf[v], w, op % 2);
		}
	}
	for(int i = 1; i <= n; i++) {
		g[leaf[i]].push_back({leaf[i] + D, 0}),g[leaf[i] + D].push_back({leaf[i], 0});
	}
	dijkstra();
	for(int i = 1; i <= n; i++) {
		if(dist[leaf[i]] == 0x3f3f3f3f3f3f3f3f) cout << -1 << " \n" [i == n];
		else cout << dist[leaf[i]] << " \n" [i == n];
	}
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T = 1;
	if (multi) cin >> T;
	while (T--) {
		solve();
	}
	
	return 0;
}

前后缀建图优化

2-SAT问题

题意：你有 n 张卡片，第 i 张卡片正面写着一个数字 ai，反面写着一个数字 bi，现在你可以摆放卡片（规定每张卡片朝上的面），询问是否存在一种摆放方式，使得任意两张不同的卡片朝上面所写的数字都是互质的。

两排结点，上面那排每个都分别往左连（前缀），下面那排每个都分别往右连（后缀）

这时向前缀中的一个结点连相当于向这个结点以及之前的所有点连。

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
127
128
129
130
// Problem: F - Coprime Solitaire
// Contest: AtCoder - AtCoder Beginner Contest 210
// URL: https://atcoder.jp/contests/abc210/tasks/abc210_f
// Memory Limit: 1024 MB
// Time Limit: 3000 ms

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
using ll = long long;

bool multi = 0;

bool st[2000005],ispr[2000005];
int prime[2000005],pcnt;
void get_primes(int n){
    for(int i=2;i<=n;i++)
    {
        if(!st[i]) prime[pcnt++]=i;
        for(int j=0;prime[j]<=n/i;j++){
            st[prime[j]*i]=true;
            if(i%prime[j]==0) break;
        }
    }
}

int n;
int a[30005], b[30005];

vector<int> v[2000005];
int nw;

const int N = 20000005, M = 20000005;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], ts, stk[N], top;
int id[N], cnt;
bool ins[N];

void add(int a, int b) {
	e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void tarjan(int u) {
	dfn[u] = low[u] = ++ ts;
	stk[++top] = u, ins[u] = true;
	for(int i = h[u]; ~i; i = ne[i]) {
		int j = e[i];
		if(!dfn[j]) {
			tarjan(j);
			low[u] = min(low[u], low[j]);
		}else if(ins[j]) low[u] = min(low[u], dfn[j]);
	}
	if(low[u] == dfn[u]) {
		int y;
		cnt++;
		do {
			y = stk[top--], ins[y] = false, id[y] = cnt;
		}while(y != u);
	}
}

int nt(int x) {
	return x > n ? x - n : x + n;
}

void solve() {
	memset(h, -1, sizeof h);
	get_primes(2000002);
	for(int i = 0; i < pcnt; i++) {
		ispr[prime[i]] = true;
	}
	cin >> n;
	nw = n * 2;
	for(int i = 1; i <= n; i++) {
		cin >> a[i] >> b[i];
	}
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= a[i] / j; j++) {
			if(a[i] % j == 0) {
				if(ispr[j]) v[j].push_back(i);
				else if(ispr[a[i] / j]) v[a[i] / j].push_back(i);
			}
		}
		for(int j = 1; j <= b[i] / j; j++) {
			if(b[i] % j == 0) {
				if(ispr[j]) v[j].push_back(i + n);
				else if(ispr[b[i] / j]) v[b[i] / j].push_back(i + n);
			}
		}
	}
	
	for(int i = 1; i <= 2000000; i++) {
		for(int j = 0; j < v[i].size(); j++) {
			++nw;
			add(nw, nt(v[i][j]));
			if(j) add(v[i][j], nw - 1), add(nw, nw - 1);
		}
		for(int j = (int)v[i].size() - 1; j >= 0; j--) {
			++nw;
			add(nw, nt(v[i][j]));
			if(j < (int)v[i].size() - 1) add(v[i][j], nw - 1), add(nw, nw - 1);
		}
	}
	for(int i = 1; i <= n * 2; i++) {
		if(!dfn[i]) {
			tarjan(i);
		}
	}
	for(int i = 1; i <= n; i++) {
		// cout << id[i] << ' ' << id[i + n] << '\n';
		if(id[i] == id[i + n]) {
			cout << "No\n";
			return;
		}
	}
	cout << "Yes\n";
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T = 1;
	if (multi) cin >> T;
	while (T--) {
		solve();
	}
	
	return 0;
}