Loj 6541 圣杯战争

Posted on | Views:

动态开点线段树 + 可删堆.

首先由于边权都是 $>0$ 的,易知答案一定是最小生成树上的一条边,用反证法不难证明.

先做出一棵最小生成树,并钦定一个点为根,对每个点 $x$ 维护一个 ${\rm res}(x)$ ,表示 $x$ 的所有异色儿子与 $x$ 的最短距离,没有异色儿子则视为 $\inf$ ,那么答案就是 $\min_x \lbrace{\rm res}(x)\rbrace$ .

每次修改 $x$ 的颜色时,会影响到 ${\rm res}(x),{\rm res}(fa(x))$ ,我们用一个可删小根堆维护所有的 ${\rm res}(x)$ ,修改时将 ${\rm res}(x),{\rm res}(fa(x))$ 从堆中删掉,计算出新的 ${\rm res}(x),{\rm res}(fa(x))$ 后再将它们加入到堆中,查询堆顶即为答案.

对每个 $x$ 开一棵以颜色为下标的线段树,为每个叶子节点开一个可删小根堆,对于 $x$ 的每个儿子 $y$ ,将 $(x,y)$ 的边权加入到 $col(y)$ 对应的堆中,计算 ${\rm res}(x)$ 时只需查询 $[1,col(x)),(col(x),K]$ 这两个区间内叶子节点堆顶的最小值.

修改 $x$ 的颜色时需要对 $fa(x)$的线段树修改,将原来颜色的贡献删掉,将新的颜色的贡献加入.

叶子节点不会超过 $n+q$ 个,可删堆就只需要开这么多个,如果开 $O((n+q)\log (n+q))$ 个可能会 RE 或 CE.

时间复杂度 $O(m\log m+(n+q)\log (n+q))$ .

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
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
//%std
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out = 0, fh = 1;
	char jp = getchar();
	while ((jp > '9' || jp < '0') && jp != '-')
		jp = getchar();
	if (jp == '-')
		fh = -1, jp = getchar();
	while (jp >= '0' && jp <= '9')
		out = out * 10 + jp - '0', jp = getchar();
	return out * fh;
}
void print(int x)
{
	if (x >= 10)
		print(x / 10);
	putchar('0' + x % 10);
}
void write(int x, char c)
{
	if (x < 0)
		putchar('-'), x = -x;
	print(x);
	putchar(c);
}
const int N = 4e5 + 10, inf = 1e9;
struct Heap
{
	priority_queue<int> q1, q2;
	void insert(int x)
	{
		q1.push(-x);
	}
	void erase(int x)
	{
		q2.push(-x);
	}
	int mi()
	{
		while (!q2.empty() && q1.top() == q2.top())
			q1.pop(), q2.pop();
		if (q1.empty())
			return inf;
		return -q1.top();
	}
} ans;
int n, m, q, col[N], res[N], opt_x[N], opt_k[N], val[N], tot = 0;
struct Edge
{
	int u, v, w;
	bool operator < (const Edge &rhs) const
	{
		return w < rhs.w;
	}
} E[N];
vector<pair<int, int> > G[N];
int Fa[N], fa[N], tofa[N];
int Find(int x)
{
	return x == Fa[x] ? x : Fa[x] = Find(Fa[x]);
}
int idx = 0, mi[N * 2] = {inf}, ls[N * 2], rs[N * 2], id[N * 2], t = 0, rt[N];
Heap leaf[N];
void upd(int &x, int l, int r, int pos, int c, int sgn)
{
	if (!x)
		x = ++idx;
	if (l == r)
	{
		if (!id[x])
			id[x] = ++t;
		if (sgn == 1)
			leaf[id[x]].insert(c);
		else
			leaf[id[x]].erase(c);
		mi[x] = leaf[id[x]].mi();
		return;
	}
	int mid = (l + r) >> 1;
	if (pos <= mid)
		upd(ls[x], l, mid, pos, c, sgn);
	else
		upd(rs[x], mid + 1, r, pos, c, sgn);
	mi[x] = min(mi[ls[x]], mi[rs[x]]);
}
void query(int &s, int x, int l, int r, int L, int R)
{
	if (!x || L > R)
		return;
	if (L <= l && r <= R)
	{
		s = min(s, mi[x]);
		return;
	}
	int mid = (l + r) >> 1;
	if (L <= mid)
		query(s, ls[x], l, mid, L, R);
	if (R > mid)
		query(s, rs[x], mid + 1, r, L, R);
}
void dfs(int x, int F)
{
	fa[x] = F, res[x] = inf;
	for (auto p : G[x])
	{
		int y = p.first, w = p.second;
		if (y == F)
			continue;
		if (col[y] != col[x])
			res[x] = min(res[x], w);
		upd(rt[x], 1, tot, col[y], w, 1);
		tofa[y] = w;
		dfs(y, x);
	}
	ans.insert(res[x]);
}
int main()
{
	n = read(), m = read(), read(), q = read();
	for (int i = 1; i <= m; ++i)
		E[i].u = read(), E[i].v = read(), E[i].w = read();
	sort(E + 1, E + 1 + m);
	iota(Fa + 1, Fa + 1 + n, 1);
	for (int i = 1; i <= m; ++i)
	{
		int u = Find(E[i].u), v = Find(E[i].v);
		if (u != v)
		{
			Fa[u] = v;
			G[E[i].u].push_back(make_pair(E[i].v, E[i].w));
			G[E[i].v].push_back(make_pair(E[i].u, E[i].w));
		}
	}
	for (int i = 1; i <= n; ++i)
		val[++tot] = col[i] = read();
	for (int i = 1; i <= q; ++i)
	{
		opt_x[i] = read();
		val[++tot] = opt_k[i] = read();
	}
	sort(val + 1, val + 1 + tot);
	tot = unique(val + 1, val + 1 + tot) - val - 1;
	for (int i = 1; i <= n; ++i)
		col[i] = lower_bound(val + 1, val + 1 + tot, col[i]) - val;
	dfs(1, 0);
	for (int i = 1; i <= q; ++i)
	{
		int x = opt_x[i], c = lower_bound(val + 1, val + 1 + tot, opt_k[i]) - val;
		ans.erase(res[x]);
		res[x] = inf;
		query(res[x], rt[x], 1, tot, 1, c - 1);
		query(res[x], rt[x], 1, tot, c + 1, tot);
		ans.insert(res[x]);
		if (x != 1)
		{
			ans.erase(res[fa[x]]);
			upd(rt[fa[x]], 1, tot, col[x], tofa[x], -1);
			upd(rt[fa[x]], 1, tot, c, tofa[x], 1);
			res[fa[x]] = inf;
			query(res[fa[x]], rt[fa[x]], 1, tot, 1, col[fa[x]] - 1);
			query(res[fa[x]], rt[fa[x]], 1, tot, col[fa[x]] + 1, tot);
			ans.insert(res[fa[x]]);
		}
		col[x] = c;
		write(ans.mi(), '\n');
	}
	return 0;
}