CF464E The Classic Problem

CF464E The Classic Problem

最短路，显然不具备单 $\log$ 做法，考虑维护高精二进制数，支持单点加一。

显然高精不行，维护二进制数的 trie 较为复杂，考虑本质相同的值域线段树。

支持比较大小、区间赋零和单点赋一操作。

分别想，比较大小，即维护区间哈希值，先比较高位大小是否相同，若相等递归低位；否则递归高位判断。

对于区间赋零，永久化标记过于麻烦，找到对应的 $\log$ 个区间，接上提前预处理好的全零子树即可。

对于单点赋一，板子不讲。

最后考虑空间问题，回顾最短路算法松弛，$di{s}_v$ 会用到 $di{s}_u$ 绝大部分值，可持久化一下即可。

时间复杂度 $\mathcal{O}(n{\log }^{2}n)$。

#include
using namespace std;
typedef long long ll;
#define ha putchar(' ')
#define he putchar('\n')
inline int read()
{
	int x = 0;
	char c = getchar();
	while (c < '0' || c > '9')c = getchar();
	while (c >= '0' && c <= '9')
		x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
	return x;
}
inline void write(int x)
{
	if(x < 0) putchar('-'), x = -x;
	if(x > 9) write(x / 10);
	putchar(x % 10 + 48);
}
#define lc(o) tr[o].lc
#define rc(o) tr[o].rc
#define s(o) tr[o].s
#define si(o) tr[o].si
#define hs(o) tr[o].hs
const int _ = 1e5 + 100, N = 1e5 + 20, mod = 1e9 + 7;
int n, m, s, t, cnt, p2[_], rt[_];
int tot, head[_], to[_ << 1], nxt[_ << 1], w[_ << 1];
bool vis[_]; int zct, zc[_], pre[_];
struct abc
{
	int s, si, lc, rc; ll hs;
} tr[_ * 80];
void add(int u, int v, int d) {to[++tot] = v, nxt[tot] = head[u], w[tot] = d, head[u] = tot;}
void pushup(int o)
{
	s(o) = s(lc(o)) + s(rc(o));
	hs(o) = (p2[si(lc(o))] * hs(rc(o)) % mod + hs(lc(o))) % mod;
}
void build(int &o, int l, int r)
{
	o = ++cnt, si(o) = r - l + 1;
	if(l == r) return;
	int mid = (l + r) >> 1;
	build(lc(o), l, mid), build(rc(o), mid + 1, r);
	pushup(o);
}
void upd1(int &a, int b, int l, int r, int x)
{
	a = ++cnt, tr[a] = tr[b];
	if(l == r) return s(a)++, hs(a)++, void();
	int mid = (l + r) >> 1;
	x <= mid ? upd1(lc(a), lc(b), l, mid, x) : upd1(rc(a), rc(b), mid + 1, r, x);
	pushup(a);
}
void upd2(int &a, int b, int p0, int l, int r, int L, int R)
{
	if(L <= l && r <= R) return a = p0, void();
	a = ++cnt, tr[a] = tr[b];
	int mid = (l + r) >> 1;
	if(L <= mid) upd2(lc(a), lc(b), lc(p0), l, mid, L, R);
	if(R > mid) upd2(rc(a), rc(b), rc(p0), mid + 1, r, L, R);
	pushup(a);
}
int qry(int o, int l, int r, int L, int R)
{
	if(L <= l && r <= R) return s(o);
	int mid = (l + r) >> 1, ret = 0;
	if(L <= mid) ret = qry(lc(o), l, mid, L, R);
	if(R > mid) ret += qry(rc(o), mid + 1, r, L, R);
	return ret;
}
int find(int o, int l, int r, int x, int c)
{
	if(l == r) return l;
	int mid = (l + r) >> 1;
	if(s(lc(o)) >= mid - x + 1 + c) return find(rc(o), mid + 1, r, x, c - s(lc(o)));
	return find(lc(o), l, mid, x, c);
}
void upd(int &a, int b, int x)
{
	int c = x > 0 ? qry(b, 0, N, 0, x - 1) : 0;
	int y = find(b, 0, N, x, c);
	if(y > x) upd2(a, b, rt[0], 0, N, x, y - 1);
	else a = b;
	upd1(a, a, 0, N, y);
}
bool cmp(int a, int b, int l, int r)
{
	if(l == r) return s(a) > s(b);
	int mid = (l + r) >> 1;
	if(hs(rc(a)) == hs(rc(b))) return cmp(lc(a), lc(b), l, mid);
	return cmp(rc(a), rc(b), mid + 1, r);
}
struct Node
{
	int id, rt;
	bool operator < (const Node &t) const{return cmp(rt, t.rt, 0, N);}
}; priority_queue<Node> q;
void dij(int s)
{
	build(rt[0], 0, N), rt[s] = rt[0];
	q.push({s, rt[s]});
	while(!q.empty())
	{
		int nw = q.top().id;
		q.pop();
		if(vis[nw]) continue;
		vis[nw] = 1;
		if(nw == t) break;
		for(int i = head[nw]; i; i = nxt[i])
		{
			int v = to[i];
			upd(rt[n + 1], rt[nw], w[i]);
			if(!rt[v] || cmp(rt[v], rt[n + 1], 0, N))
			{
				rt[v] = rt[n + 1];
				pre[v] = nw;
				if(!vis[v]) q.push({v, rt[v]});
			}
		}
	}
}

signed main()
{
	p2[0] = 1; for(int i = 1; i < N; ++i) p2[i] = p2[i - 1] * 2ll % mod;
	n = read(), m = read();
	for(int i = 1, u, v, w; i <= m; ++i)
	{
		u = read(), v = read(), w = read();
		add(u, v, w), add(v, u, w);
	}
	s = read(), t = read();
	dij(s);
	if(!vis[t]) return write(-1), he, 0;
	write(hs(rt[t])), he;
	zc[zct = 1] = t;
	while(t != s)
	{
		t = pre[t];
		zc[++zct] = t;
	}
	write(zct), he;
	for(int i = zct; i >= 1; --i)
		write(zc[i]), ha;
	return 0;
}
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
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148