2019牛客多校三 A. Graph Games (图分块)

大意: 给定无向图, 定义$S(x)$为$x$的邻接点集合. 每次操作翻转$[L,R]$范围的边, 询问$S(x)$与$S(y)$是否相等.

快速判断集合相等可以用$CF 799F$的技巧. 采用$hash$, 对每个数取一个随机$ull$, 转为判断异或和是否相等.

然后考虑度数分块.

对于轻点, 一个想法是查询时暴力枚举邻接边, 树状数组判断是否存在. 这样的话复杂度还带$log$很难卡过.

一个更好的做法是用分块代替树状数组实现$O(1)$查询.

对于重点, 可以对每个重点用$vector$存邻接边, 每次更新对一个重点$x$的贡献是$x$的$vector$内连续的一段, 但是这样需要二分来确定位置.

一个更好的做法是考虑对边分块, 预处理出每个块对每个重点的影响, 然后修改时对边界暴力, 整块打标记. 查询时暴力查询每块的标记即可.

#include <iostream>

#include <random>

#include <cstdio>

#include <math.h>

#define REP(i,a,n) for(int i=a;i<=n;++i)

#define PER(i,a,n) for(int i=n;i>=a;--i)

#define pb push_back

#define x first

#define y second

using namespace std;

typedef unsigned long long ull;

typedef pair<int,int> pii;

const int N = 2e5+10;

int n, m, u[N], v[N], deg[N];

char ans[N];

vector<pii> small[N];

int S,c1[N],c2[N],c3[N],ID[N];

ull f[800][800];

ull a[N],s[N];

void upd(int x) {

	REP(i,x/S*S,x) c1[i]^=1,s[u[i]]^=a[v[i]],s[v[i]]^=a[u[i]];

	PER(i,0,x/S-1) c2[i]^=1,c3[i]^=1;

}

ull query(int x) {

	return c1[x]^c2[x/S];

}

ull qry(int x) {

	ull ans = 0;

	if (ID[x]) {

		PER(i,0,m/S) if (c3[i]) ans ^= f[i][ID[x]];

		return ans^s[x];

	}

	for (auto e:small[x]) if (query(e.x)) ans ^= a[e.y];

	return ans;

}

std::mt19937 rd(time(0));

void work() {

	scanf("%d%d", &n, &m), S = 1.5*sqrt(m);

	REP(i,0,m+5) c1[i]=c2[i]=c3[i]=0;

	REP(i,0,n+5) s[i]=ID[i]=deg[i]=0,small[i].clear();

	REP(i,1,m) {

		scanf("%d%d", u+i, v+i);

		++deg[u[i]],++deg[v[i]];

	}

	upd(m);

	REP(i,1,n) if (deg[i]>=S) ID[i]=++*ID;

	PER(i,0,m/S) REP(j,0,*ID) f[i][j]=0;

	if (S>=800) throw;

	if (*ID>=800) throw;

	if (m/S>=800) throw;

	REP(i,1,m) {

		int id = i/S;

		if (ID[u[i]]) f[id][ID[u[i]]]^=a[v[i]];

		else small[u[i]].pb(pii(i,v[i]));

		if (ID[v[i]]) f[id][ID[v[i]]]^=a[u[i]];

		else small[v[i]].pb(pii(i,u[i]));

	}

	int q, cnt = 0;

	scanf("%d", &q);

	while (q--) {

		int op, x, y;

		scanf("%d%d%d", &op, &x, &y);

		if (op==1) upd(y),upd(x-1);

		else ans[++cnt] = qry(x)==qry(y)?'1':'0';

	}

	ans[cnt+1] = 0;

	puts(ans+1);

}

int main() {

	REP(i,0,N-1) a[i] = rd()*rd();

	int t;

	scanf("%d", &t);

	while (t--) work();

}

巴特西

2019牛客多校三 A. Graph Games (图分块)

最新文章

热门文章