RE 求调 代码清新
查看原帖
RE 求调 代码清新
224663
kintsgi楼主2023/12/29 15:48
#include <bits/stdc++.h>
#define mk make_pair
#define pb emplace_back
#define fi first
#define se second
#define pii pair<int, int>
#define fore(i, u) for (int i = h[u]; i; i = e[i].nxt)
#define all(x) x.begin(), x.end()

using namespace std;
inline int read() {
	int x = 0, f = 1;
	char ch = getchar();
	while (! isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); }
	while (isdigit(ch)) { x = x * 10 + ch - 48; ch = getchar(); }
	return x * f;
}

const int maxn = 4e5 + 10; int n, m, q, le, lc, lq, lch;
int chk[maxn], l[maxn], r[maxn], ans[maxn], vis[maxn], nw[maxn];

struct Node { int u, v, w; } e[maxn], ve[maxn];
struct Qry { int id, op, x, v; } t[maxn], vc[maxn], vq[maxn];

namespace uniset {
	int tp, fa[maxn], sz[maxn]; pii st[maxn];
	int fnd(int x) { return x == fa[x] ? x : fnd(fa[x]); }
	void reset() { for (int i = 1; i <= n; i ++) fa[i] = i, sz[i] = 1; }
	void undo(int id) { while (tp ^ id) { auto [x, y] = st[tp --]; sz[x] -= sz[y], fa[y] = y; } }
	void merg(int x, int y) {
		x = fnd(x), y = fnd(y);
		if (x ^ y) { if (sz[x] < sz[y]) swap(x, y);
			st[++ tp] = mk(x, y), sz[x] += sz[y], fa[y] = x; }
	}
}

int main() {
	
	n = read(), m = read();
	for (int i = 1; i <= m; i ++) e[i] = Node {read(), read(), read()};
	q = read(); for (int i = 1; i <= q; i ++) t[i] = Qry {i, read(), read(), read()};

	const int B = 1400, T = (q - 1) / B + 1;
	for (int i = 1; i <= T; i ++) l[i] = (i - 1) * B + 1, r[i] = min(q, i * B);
	
	memset(ans, -1, sizeof ans);
	for (int i = 1; i <= T; i ++) {
		uniset :: reset(), lc = lq = le = lch = 0;
		
		for (int j = l[i]; j <= r[i]; j ++)	
			if (t[j].op - 1) vq[++ lq] = t[j];
			else vc[++ lc] = t[j], vis[t[j].x] = 1;
		
		for (int j = 1; j <= m; j ++) if (!vis[j]) ve[++ le] = e[j]; else chk[++ lch] = j;
		sort(ve + 1, ve + le + 1, [](Node x, Node y) { return x.w > y.w; });
		sort(vq + 1, vq + lq + 1, [](Qry x, Qry y) { return x.v > y.v; });
		
		int pt = 1;
		for (int p = 1; p <= lq; p ++) {
			auto [iq, _, s, w] = vq[p];
			for (int j = 1; j <= lch; j ++) nw[chk[j]] = e[chk[j]].w;
			while (pt <= le && ve[pt].w >= w) uniset :: merg(ve[pt].u, ve[pt].v), pt ++;
			
			int re = uniset :: tp;
			for (int j = 1; j <= lc; j ++) if (vc[j].id < iq) nw[vc[j].x] = vc[j].v;
			for (int j = 1; j <= lch; j ++) { int id = chk[j];
				if (nw[id] >= w) uniset :: merg(e[id].u, e[id].v); }

			ans[iq] = uniset :: sz[uniset :: fnd(s)];
			uniset :: undo(re);
		}

		sort(vc + 1, vc + lc + 1, [](Qry x, Qry y) { return x.id < y.id; });
		for (int j = l[i]; j <= r[i]; j ++)	vis[t[j].x] = 0;
		for (int j = 1; j <= lc; j ++) e[vc[j].x].w = vc[j].v;
	}
	
	for (int i = 1; i <= q; i ++) if (~ans[i]) printf("%d\n", ans[i]);

	return 0;
}
2023/12/29 15:48
加载中...