经过一系列卡空间之后，这是我的F代码

cjdst

2025-07-19 07:22:33

发布于：湖南

36阅读

0回复

0点赞

由于本题空间特别的小（256 MB），所以考虑时间换空间。

将块长调小，这样可以使更多的节点进入直接计算的行列，减少在哈希表中新添元素的次数，进而减小空间。

令块长为 $l$ 。则时间复杂度： $O(ql+\frac{nq}{l})$ ，空间复杂度 $O(\min\{ql,\frac{nq}{l}\})$ 。

不会弄块长，乱搞了个 $189$ ，但是跑得飞快。

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <iostream>
#include <random>
#include <cstdio>
#include <vector>
#include <cmath>
#include <ctime>
#define int long long

using namespace __gnu_pbds;
using namespace std;

mt19937 rng;
unsigned s1, s2, s3;

int a[200005]; 
vector <pair <int, int>> v[200005];

int siz;
vector <int> big;
int idx[200005];
vector <pair <int, int>> v2[200005];
gp_hash_table <unsigned int, int> cont_small;

unsigned int get_ee(int x, int y){//乱搞，不会哈希 
	unsigned int cur = x * 200005 + y;
	cur += s1;
	cur = (cur ^ (x >> 33)) * s2;
	cur = (cur ^ (x >> 30)) * s3;
	//cout << cur << '\n';
	return cur;
}

int count_cont(int idx, int val){//优化，有较多相邻节点的节点之间直接计算
	int ans = 0;
	for(auto i:v2[idx]){
		if(a[i.first] == val) ans += i.second;
	}
	//cout << ans << ' ';
	return ans;
}

void solve(){
	int n, m;
	cin >> n >> m;
	siz = 189;//sqrtn -> 233 -> 189
	for(int i = 1; i <= n; i++) cin >> a[i];
	int ans = 0;
	
	for(int i = 1; i < n; i++){
		int x, y, z;
		cin >> x >> y >> z;
		v[x].push_back({y, z});
		v[y].push_back({x, z});
		if(a[x] != a[y]) ans += z;
	}
	
	for(int i = 1; i <= n; i++){
		if(v[i].size() >= siz){
			big.push_back(i), idx[i] = big.size() - 1;
		}
	}
	
	for(int i = 1; i <= n; i++){
		for(auto j:v[i]){
			if(v[j.first].size() >= siz){
				v2[i].push_back(j);
				if(v[i].size() < siz) cont_small[get_ee(idx[j.first], a[i])] += j.second;
			}
		}
	}
	//cout << ans << '\n';
	
	while(m--){
		int x, y;
		cin >> x >> y;
		if(v[x].size() < siz){
			for(auto i:v[x]){
				if(a[i.first] != a[x]) ans -= i.second;
				if(a[i.first] != y) ans += i.second;
			}
			for(auto i:v2[x]){
				cont_small[get_ee(idx[i.first], a[x])] -= i.second;
				cont_small[get_ee(idx[i.first], y)] += i.second;
			}
		}else{
			ans += cont_small[get_ee(idx[x], a[x])] + count_cont(x, a[x]);
			ans -= cont_small[get_ee(idx[x], y)] + count_cont(x, y);
		}
		a[x] = y;
		cout << ans << '\n';
	}
	
	for(int i = 1; i <= n; i++){
		v[i].clear();
		v2[i].clear();
		idx[i] = 0;
	}
	cont_small.clear();
	big.clear();
} 
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	rng.seed(time(0));
	s1 = rng(), s2 = rng(), s3 = rng();
	int t;
	cin >> t;
	while(t--) solve();
	
	return 0;
}