crazy_cloud's Blog
0%

ONTAK2015, BZOJ4298 Bajtocja

Posted on Edited on In

题目大意

给定 \(d\) 张无向图，每张图都有 \(n\) 个点。一开始，在任何一张图中都没有任何边。

接下来有 \(m\) 次操作，每次操作会给出 \(a,b,k\)，意为在第 \(k\) 张图中的点 \(a\) 和点 \(b\) 之间添加一条无向边。

你需要在每次操作之后输出有序数对 \((a,b)\) 的个数，使得 \(1\leq a,b\leq n\)，且 \(a\) 点和 \(b\) 点在 \(d\) 张图中都连通。

\(1\leq d\leq200,1\leq n\leq5000,1\leq m\leq 10^6\)

题目分析

设 \(f(x,i)\) 表示点 \(x\) 在第 \(i\) 张图里面的连通块编号，这个在有加边操作时可以使用启发式合并来快速地更新。

如果 \(x\) 和 \(y\) 两个点在所有图里面都联通，显然 \(\forall 1\leq i\leq d,f(x,i)=f(y,i)\)。

考虑对每一个 \(x\) 都维护所有 \(f(x,i)\) 的哈希值，然后再使用一个哈希表来找到相同哈希值的点的个数就能求答案了。

时间复杂度 \(O(dn \log n+m)\)。

代码实现

一开始写的时候以为哈希表可以直接删除元素结果调了半天……简直智障 qwq

不知为什么运行效率垫底。

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
#include <algorithm>
#include <iostream>
#include <vector>
#include <cstdio>
#include <cctype>

using namespace std;

inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while (!isdigit(ch)) f=ch=='-'?-1:f,ch=getchar();
	while (isdigit(ch)) x=x*10+ch-'0',ch=getchar();
	return x*f;
}

int buf[30];

inline void write(int x)
{
	if (x<0) putchar('-'),x=-x;
	for (;x;x/=10) buf[++buf[0]]=x%10;
	if (!buf[0]) buf[++buf[0]]=0;
	for (;buf[0];putchar('0'+buf[buf[0]--]));
}

const int MOD1=330301441;
const int MOD2=1004535809;
const int MOD=7340033;
const int P1=269;
const int P2=467;

typedef pair<int,int> P;
typedef pair<P,int> data;
#define mkp(a,b) make_pair(a,b)
#define ft first
#define sd second

inline P operator+(P x,P y){return mkp((x.ft+y.ft)%MOD1,(x.sd+y.sd)%MOD2);}
inline P &operator+=(P &x,P const y){return x=x+y;}
inline P operator-(P const x){return mkp(MOD1-x.ft,MOD2-x.sd);}
inline P operator-(P x,P y){return x+(-y);}
inline P &operator-=(P &x,P const y){return x=x-y;}
inline P operator*(P x,P y){return mkp(1ll*x.ft*y.ft%MOD1,1ll*x.sd*y.sd%MOD2);}
inline P &operator*=(P &x,P const y){return x=x*y;}

const int D=205;
const int N=5005;
const int S=D*N;

vector<int> component[S];
data list[2][MOD];
int fa[S];
P hash[N];
P POW[D];
int d,n,m,ans;

int getfather(int son){return fa[son]==son?son:fa[son]=getfather(fa[son]);}

inline int sqr(int x){return x*x;}

inline void getposition(P h,bool &flag,int &pos)
{
	int itr0=h.ft%MOD,itr1=h.sd%MOD;
	for (;list[0][itr0].ft!=mkp(-1,-1)&&list[0][itr0].ft!=h&&list[1][itr1].ft!=mkp(-1,-1)&&list[1][itr1].ft!=h;(++itr0)%=MOD,(++itr1)%=MOD);
	if (list[0][itr0].ft==mkp(-1,-1)||list[0][itr0].ft==h) flag=0,pos=itr0;
	else flag=1,pos=itr1;
}

inline void remove(P h)
{
	bool flag;int pos;
	getposition(h,flag,pos),ans-=sqr(list[flag][pos].sd),ans+=sqr(--list[flag][pos].sd);
}

inline void insert(P h)
{
	bool flag;int pos;
	getposition(h,flag,pos),ans-=sqr(list[flag][pos].sd),list[flag][pos].ft=h,ans+=sqr(++list[flag][pos].sd);
}

int main()
{
	freopen("bajtocja.in","r",stdin),freopen("bajtocja.out","w",stdout);
	for (int i=0;i<MOD;++i) list[0][i]=list[1][i]=mkp(mkp(-1,-1),0);
	d=read(),n=read(),m=read();
	POW[0]=mkp(1,1);
	for (int i=1;i<=d;++i) POW[i]=POW[i-1]*mkp(P1,P2);
	for (int x=1;x<=d*n;++x) fa[x]=x,component[x].push_back((x-1)%n+1);
	for (int x=1;x<=n;++x)
	{
		hash[x]=mkp(0,0);
		for (int i=0;i<d;++i) hash[x]+=mkp(x,x)*POW[i];
		insert(hash[x]);
	}
	for (int i=1,id,x,y,fx,fy;i<=m;++i)
	{
		x=read(),y=read(),id=read()-1,fx=getfather(x+id*n),fy=getfather(y+id*n);
		if (fx!=fy)
		{
			if (component[fx].size()<component[fy].size()) swap(x,y),swap(fx,fy);
			fa[fy]=fx;
			for (vector<int>::iterator it=component[fy].begin();it!=component[fy].end();++it)
			{
				int p=*it;
				remove(hash[p]),hash[p]-=POW[id]*mkp((fy-1)%n+1,(fy-1)%n+1);
				hash[p]+=POW[id]*mkp((fx-1)%n+1,(fx-1)%n+1),insert(hash[p]);
				component[fx].push_back(p);
			}
			component[fy].resize(0),component[fy].reserve(0);
		}
		write(ans),putchar('\n');
	}
	fclose(stdin),fclose(stdout);
	return 0;
}