文档章节

【CF938G】Shortest Path Queries(线段树分治,并查集,线性基)

o
 osc_1ee7cxmx
发布于 2018/08/06 20:37
字数 842
阅读 7
收藏 0

精选30+云产品,助力企业轻松上云!>>>

#【CF938G】Shortest Path Queries(线段树分治,并查集,线性基) ##题面 CF 洛谷 ##题解 吼题啊。 对于每个边,我们用一个$map$维护它出现的时间, 发现询问单点,边的出现时间是区间,所以线段树分治。 既然路径最小值就是异或最小值,并且可以不是简单路径, 不难让人想到$WC2011$那道最大$Xor$路径和。 用一样的套路,我们动态维护一棵生成树,碰到一个非树边, 就把这个环的异或和丢到线性基里面去,这样子直接查就好了。 动态维护生成树直接用并查集就好了,没有必要$LCT$ 大概就是永远不进行路径压缩,每次启发式合并。 询问的时候暴跳父亲。 然后撤销操作的话,维护一个栈,每次存下当前的修改操作, 撤销的时候倒序还原就好了。 细节很多,第一次写这样的东西,调了好久啊。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
#define MAX 200200
#define ll long long
#define pi pair<int,int>
#define mp(x,y) make_pair(x,y)
#define lson (now<<1)
#define rson (now<<1|1)
inline int read()
{
	int x=0;bool t=false;char ch=getchar();
	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
	if(ch=='-')t=true,ch=getchar();
	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
	return t?-x:x;
}
struct xxj
{
	int p[31];
	void insert(int x)
		{
			for(int i=30;~i;--i)
				if(x&(1<<i))
				{
					if(!p[i]){p[i]=x;break;}
					x^=p[i];
				}
		}
	int Query(int x){for(int i=30;~i;--i)x=min(x,x^p[i]);return x;}
}G;
struct Node{int u,v,w;}p[MAX<<1];
pi q[MAX];
int n,m;
map<pi,int> M;
vector<Node> seg[MAX<<2];
void Modify(int now,int l,int r,int L,int R,Node e)
{
	if(L>R)return;if(L<=l&&r<=R){seg[now].push_back(e);return;}
	int mid=(l+r)>>1;
	if(L<=mid)Modify(lson,l,mid,L,R,e);
	if(R>mid)Modify(rson,mid+1,r,L,R,e);
}
int tim,cnt,L[MAX<<1],R[MAX<<1];
int f[MAX],sz[MAX],Xor[MAX];
int getf(int x){while(x!=f[x])x=f[x];return x;}
int getxor(int x){int ret=0;while(x!=f[x])ret^=Xor[x],x=f[x];return ret;}
void Divide(int now,int l,int r,xxj G)
{
	vector<Node> c;c.clear();
	for(int i=0,lim=seg[now].size();i<lim;++i)
	{
		int u=seg[now][i].u,v=seg[now][i].v,w=seg[now][i].w;
		int f1=getf(u),f2=getf(v);
		if(f1==f2)G.insert(getxor(u)^getxor(v)^w);
		else
		{
			if(sz[f1]>sz[f2])swap(f1,f2),swap(u,v);
			w^=getxor(v)^getxor(u);
			c.push_back((Node){f1,f2,sz[f2]});
			Xor[f1]=w;f[f1]=f2;sz[f2]+=sz[f1];
		}
	}
	if(l==r)
		printf("%d\n",G.Query(getxor(q[l].first)^getxor(q[l].second)));
	else
	{
		int mid=(l+r)>>1;
		Divide(lson,l,mid,G);Divide(rson,mid+1,r,G);
	}
	for(int i=c.size()-1;~i;--i)
	{
		int u=c[i].u,v=c[i].v,w=c[i].w;
		sz[v]=w;f[u]=u;Xor[u]=0;
	}
}
int main()
{
	//freopen("938G.in","r",stdin);
	//freopen("938G.out","w",stdout);
	n=read();m=read();
	for(int i=1;i<=m;++i)
	{
		int x=read(),y=read(),w=read();
		p[++cnt]=(Node){x,y,w};
		L[cnt]=1;M[mp(x,y)]=cnt;R[cnt]=-1;
	}
	int Q=read();
	for(int i=1;i<=Q;++i)
	{
		int opt=read(),x=read(),y=read();
		if(x>y)swap(x,y);
		if(opt==1)
		{
			p[++cnt]=(Node){x,y,read()};
			L[cnt]=tim+1;R[cnt]=-1;M[mp(x,y)]=cnt;
		}
		else if(opt==2)R[M[mp(x,y)]]=tim;
		else q[++tim]=mp(x,y);
	}
	for(int i=1;i<=cnt;++i)if(R[i]==-1)R[i]=tim;
	for(int i=1;i<=cnt;++i)Modify(1,1,tim,L[i],R[i],p[i]);
	for(int i=1;i<=n;++i)f[i]=i,sz[i]=1;
	Divide(1,1,tim,G);
	return 0;
}

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

设计模式(4) 建造者模式

什么是建造者模式 经典建造者模式的优缺点 对建造者模式的扩展 什么是建造者模式 建造者模式将一个复杂的对象的构建与它的表示分离,使得同样的构建过程可以创建不同的表示。创建者模式隐藏了...

zhixin9001
11分钟前
14
0
ArrayList源码分析 —— JDK8

ArrayList的特性 ArrayList内部使用数据作为存储结构,ArrayList可以理解为数组的扩展对象,封装了常用的和非常用的操作数组的方法。以及当数组长度不足以保存数组时,自动扩容数组,通常Arr...

XuePeng77
17分钟前
16
0
__slots__的用法? - Usage of __slots__?

问题: Python中__slots__的目的是什么-尤其是关于何时以及何时不使用它的目的? 解决方案: 参考一: https://stackoom.com/question/1ymu/slots-的用法 参考二: https://oldbug.net/q/1ym...

富含淀粉
28分钟前
17
0
Python分析42年高考数据,告诉你高考为什么这么难?

作者:徐麟 历年录取率 可能很多经历过高考的人都不知道高考的全称,高考实际上是普通高等学校招生全国统一考试的简称。从1977年国家恢复高考制度至今,高考经历了许多的改革,其中最为显著的...

爱码小哥
30分钟前
19
0
CKEditor 5 + SpringBoot实战(四):SpringBoot 实现文件上传

在本系列的文章中,我将介绍如何在Spring Boot Application中使用CKEditor编辑器。介绍的内容包括基本环境的搭建,文件上传,SpringData JPA数据持久化,CKEditor5的安装,CKEditor图片上传,...

树下魅狐
32分钟前
20
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部