P15534 那猫猫城的集市题解

P15534
由于每次询问是不同的货物，考虑离线。

从 $u \rightarrow v$ 和 $v \rightarrow u$ 的答案不同，我们将询问分成两段 $u \rightarrow \text{LCA}$ ， $\text{LCA} \rightarrow v$ 。

对于 $u \rightarrow \text{LCA}$ 的部分，我们在 $u$ 点将询问放入对应的货物集合，在 $\text{LCA}$ 点得到询问所在的集合。可以用并查集维护同一种货物的询问。当经过点 $x$ 时，改变代表
$a_x$ 和 $b_X$ 的集合。对于不同子树的合并则用启发式合并。

对于 $\text{LCA} \rightarrow v$ 的部分，我们仿造上面的做法，在 $LCA$ 点将询问放入，在 $u$ 点得到答案。在进入，退出点 $x$ 时，交换 $a_x$ 和 $b_x$ 的货物集合。因为自顶向下，所以不用写撤销操作，只用维护整个的货物集合。

额外讲一下 gp_hash_table 的一些问题。
下面代码在写入 $3$ 的时候可能引发重哈希，导致原本 $0$ 的位置没有了值，所以最后会输出 $0$ 。

gp_hash_table<int, int>a;
int32_t main(){
    a[0] = 1, a[1] = 2, a[2] = 3, a[3] = a[0];
    cout << a[3] << endl;
	return 0;
}

复杂度 $O(n \log n)$ ，常数较大。
代码删去了快读部分。

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define endl '\n'
#define FL(a,b,c) for(int a=(b),a##end=(c);a<=a##end;++a)
#define FR(a,b,c) for(int a=(b),a##end=(c);a>=a##end;--a)
#define lowbit(x) ((x)&-(x))
#define eb emplace_back
#define sz(x) (int)((x).size())
// #define int long long
#define vt vector
#define fr first
#define se second
bool IOS=(cin.tie(0)->sync_with_stdio(0),0);
// #define LOCAL 
#ifdef LOCAL
bool IOS1=(freopen(LOCAL".in", "r", stdin),1);
bool IOS2=(freopen(LOCAL".out", "w", stdout),1);
#endif
#define mmt(x, y) memset(x, y, sizeof x)
#define PII pair<int, int>
#define max(a, b)({auto f7r=(a);auto j3h=(b);f7r<j3h?j3h:f7r;})
#define cmax(a, b)({auto j3h=(b);(j3h>a)&&(a=j3h);})
#define min(a, b)({auto f7r=(a);auto j3h=(b);f7r>j3h?j3h:f7r;})
#define cmin(a, b)({auto j3h=(b);(j3h<a)&&(a=j3h);})
constexpr int N = 1e6 + 10;

gp_hash_table<int, int>d[N], d2;
vt<int>e[N], a1[N], a2[N], a3[N];
int n, a[N], b[N], dep[N], fa[N], lb[N], p[N], m, col[N], c[N], top;
void dfs(int x, int f){
	int w = lb[f], y = lb[w];
	dep[x] = dep[fa[x] = f] + 1, lb[x] = (dep[y] + dep[f] == dep[w] * 2) ? y : f;
	for(int&v : e[x])if(v != f)dfs(v, x);
}
int LCA(int x, int y){
	if(dep[x] < dep[y])swap(x, y);
	while(dep[x] > dep[y])x = x[dep[lb[x]] >= dep[y] ? lb : fa];
	while(x != y)
		if(lb[x] != lb[y])x = lb[x], y = lb[y];
		else x = fa[x], y = fa[y];
	return x;
}
int find(int x){return p[x] < 0 ? x : p[x] = find(p[x]);}
#define count(mp, a) ((mp).find(a) != (mp).end())
void change(auto&g, const int&a, const int&b){
	int x, y;
	if(count(g, a) && count(g, b))x = g[a], y = g[b], c[x] = b, c[y] = a, swap(g[a], g[b]);
	else if(count(g, a))x = g[a], c[g[b] = x] = b, g.erase(a);
	else if(count(g, b))x = g[b], c[g[a] = x] = a, g.erase(b);
}
void merge(int&x, int&y){
	if(x == y)return;
	if(p[x] > p[y])swap(x, y);
	p[x] += p[y], p[y] = x;
}
void dfs1(int x){
	for(auto&v : e[x])if(v != fa[x]){
		if(dfs1(v), d[x].size() < d[v].size())d[x].swap(d[v]);
		for(auto&z : d[v])
			if(count(d[x], z.fr))merge(d[x][z.fr], z.se);
			else d[x][z.fr] = z.se;
	}
	for(int&z : a1[x])
        if(count(d[x], col[z]))merge(d[x][col[z]], z);
		else d[x][col[z]] = z, c[z] = col[z];
	change(d[x], a[x], b[x]);
	for(int&z : a2[x])col[z] = c[find(z)];
}
void dfs2(int x){
	change(d2, a[x], b[x]);
	for(int&z : a2[x])
        if(count(d2, col[z]))merge(d2[col[z]], z);
		else d2[col[z]] = z, c[z] = col[z];
	for(int&z : a3[x])col[z] = c[find(z)];
	for(int&v : e[x])if(v != fa[x])dfs2(v);
	change(d2, a[x], b[x]);
}
int32_t main(){
	int u, v;
	read(n, m);
	FL(i, 1, n)read(a[i]);
	FL(i, 1, n)read(b[i]);
	FL(i, 2, n)read(u, v), e[u].eb(v), e[v].eb(u);
	dfs(1, 0);
	FL(i, 1, m)read(u, v, col[i]), a1[u].eb(i), a2[LCA(u, v)].eb(i), a3[v].eb(i);
	mmt(p, -1), dfs1(1), mmt(p, -1), dfs2(1);
	FL(i, 1, m)put(col[i], '\n');
	return 0;
}

P15534 那猫猫城的集市 题解

P15534 那猫猫城的集市题解