当前位置: 首页 > 编程日记 > 正文

[bzoj3673/3674可持久化并查集加强版]

n个集合 m个操作 操作: 1 a b 合并a,b所在集合 2 k 回到第k次操作之后的状态(查询算作操作) 3 a b 询问a,b是否属于同一集合,是则输出1否则输出0

0<n,m<=2*10^5  强制在线。

这两题一题都一样,另一题比较水,nm只有2*10^4,允许离线.....

做法很简单,把数组当作可持久化线段树那么维护,每个表示区间的节点都不存东西,每次只要新建log个节点。

我交水的那道过不去,绝望的时候我交了一发加强版居然A了,根据我多年的经验一定是有特殊数据的坑,特判了一波终于过了。

用了启发式合并之后复杂度nlog^2n

#include<iostream>
#include<cstdio>
#define MN 20000000
#define MM 200000
using namespace std;
inline int read()
{int x = 0 , f = 1; char ch = getchar();while(ch < '0' || ch > '9'){ if(ch == '-') f = -1;  ch = getchar();}while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * f;
}int cnt=0,n,m,last=0,rt[MM+5],cc;
struct data{int x,size;
}s[MM*3+5];
struct TREE{int l,r;data *x;
}T[MN];void build(int x,int l,int r)
{if(l==r){T[x].x=&s[l];return;}int mid=l+r>>1;build(T[x].l=(++cnt),l,mid);build(T[x].r=(++cnt),mid+1,r);
}data*get(int x,int k,int l=1,int r=n)
{ if(l==r)return T[x].x;int mid=l+r>>1;if(k<=mid) return get(T[x].l,k,l,mid);else return get(T[x].r,k,mid+1,r);  
}data getfa(int x,int r)
{data y=*get(r,x),ans=y;if(!y.x)return (data){x,ans.size};while(y.x) {ans=y;y=*get(r,y.x);}return (data){ans.x,y.size};
}void ins(int x,int dep,int k)
{int l=1,r=n;int nx=rt[dep]=++cnt;while(l<r){int mid=l+r>>1;if(k<=mid){T[nx].r=T[x].r;T[nx].l=++cnt;nx=T[nx].l;x=T[x].l;r=mid;}else{T[nx].l=T[x].l;T[nx].r=++cnt;nx=T[nx].r;x=T[x].r;l=mid+1;}}T[nx].x=&s[cc];
}int main()
{cc=n=read();m=read();for(int i=1;i<=n;i++)s[i]=(data){0,1};build(++cnt,1,n);rt[0]=1;for(int i=1;i<=m;i++){int a=read(),b=read()^last;if(a==2)rt[i]=rt[b];else{int c=read()^last;if(a==3) printf("%d\n",last=(getfa(b,rt[i-1]).x==getfa(c,rt[i-1]).x)),rt[i]=rt[i-1];else{data x=getfa(b,rt[i-1]),y=getfa(c,rt[i-1]);if(x.x==y.x){rt[i]=rt[i-1];continue;}if(x.size>y.size)swap(x,y);s[++cc]=(data){y.x,x.size};ins(rt[i-1],i,x.x);s[++cc]=(data){0,x.size+y.size};ins(rt[i],i,y.x);}}}return 0;
}

转载于:https://www.cnblogs.com/FallDream/p/bzoj3674.html

相关文章:

[Manthan, Codefest 18][Codeforces 1037E. Trips]

题目链接&#xff1a;1037E - Trips 题目大意&#xff1a;有n个人&#xff0c;m天&#xff0c;每天晚上都会有一次聚会&#xff0c;一个人会参加一场聚会当且仅当聚会里有至少k个人是他的朋友。每天早上都会有一对人成为好朋友&#xff0c;问每天晚上最多能有多少人参加聚会。朋…

oracle 10g undo 管理,Oracle 10g undo表空间管理

一、oracle 9i起&#xff0c;有两种undo管理方式&#xff1a;AUM Automatic Undo ManagementMUN Manual Undo Management建议使用 AUM &#xff0c;下面只讨论AUM一、Oracle 9i起&#xff0c;有两种undo管理方式&#xff1a;AUM Automatic Undo ManagementMUN Manual Undo Mana…

电子狗显示连接不上服务器,大家觉得我这样做得对吗?行车记录仪新名词:云狗...

“云”概念化已经成为新轮的市场趋势&#xff0c;些行车记录仪品牌已经加入云狗功能&#xff0c;云狗普通的电子狗有什么区别&#xff1f;“云”概念对于行车记录仪行业发展的意义何在&#xff1f;何谓“云电子狗”&#xff1f;云电子狗指通过无线互联网络具备实时与中…

织梦html引入html代码,织梦标签引入共html.doc

织梦标签引入共html1.无法在这个位置找到: {dede:include filename"织梦模板include插入非模板目录文件出现“无法在这个位置找到”错误的解决办法以下是dede V55_UTF8查dede include标签手册(3) include 引入一个文件&#xff0c;形式为&#xff1a;{dede:include file文…

AutoMapper用法

AutoMapper是对象到对象的映射工具。在完成映射规则之后&#xff0c;AutoMapper可以将源对象转换为目标对象。 作者&#xff1a;齐飞 原文&#xff1a;http://www.qeefee.com/article/automapper 配置AutoMapper映射规则 AutoMapper是基于约定的&#xff0c;因此在实用映射之前…

【洛谷习题】小A点菜

虽然也是一道dp的入门题&#xff0c;但就是想不到&#xff0c;或者说不会实现。dp还是要多做题。 链接&#xff1a;https://www.luogu.org/problemnew/show/P1164 我们可以设dp[i][j]表示以考虑完第i件&#xff0c;恰好消费j元的方案数。那么dp[i][j]dp[i-1][j]dp[i-1][j-a[i]]…

加载服务器版本信息,传奇服务器端启动加载错误的解决方法

1、启动服务端M2报错的类型2、错误分类&#xff0c;思路理清3、文字总结以下常见现象传奇服务器端启动加载错误解决方法Exception] 物品数据库加载错误![Exception] 魔法数据库加载错误!!! 地图数据加载错误.Code -1 加载Guardlist.txt时出现错误.Code -1 加载MakeItem.txt时出…

股票移动平均线matlab,股票的移动平均线 (图文)

股票的移动平均线【泸指】股票的移动平均线移动平均线是个强大的工具&#xff0c;能够更清晰地展示一系列无规律的数值变化 (比如股市波动)。此外&#xff0c;泸指移动平均线还可别除任何周期性变化(正常的季节性温度变化)的影响&#xff0c;便于我们观察到真正的趋势变化。移动…

htcd816+android密码,HTC Desire 816刷机解锁教程

一、解锁前的准备&#xff1a;1.解锁将会丢失所有数据&#xff0c;请先做好备份&#xff0c;如电话本、短信、照片、应用程序。2.下载并安装驱动程序HTC Driver。3.注册HTC Dev帐号&#xff0c;为提交解锁码做好准备。4.下载并解压 “Desire 816 解锁工具”&#xff1a;5.手机关…

BZOJ1058 [ZJOI2007]报表统计 set

原文链接https://www.cnblogs.com/zhouzhendong/p/BZOJ1058.html 题目传送门 - BZOJ1058 题解 考虑用两个 multiset 分别维护两个答案。 一个直接按照权值维护&#xff0c;另一个维护一下相邻位置的差。 比较容易想到如何维护的吧&#xff0c;不多讲&#xff0c;看代码吧。 代码…

扫描服务器端口信息工具,服务器端口扫描工具

服务器端口扫描工具 内容精选换一换2.3.2 端口扫描Internet上的大部分服务都使用一种基于TCP/IP协议的客户机/服务器的模式。在这种模式下&#xff0c;服务器端在某个TCP或UDP(User Datagram Protocol&#xff0c;用户数据报协议)的端口处于侦听状态&#xff0c;等待客户端程序…

python-Django-01基础配置

参考资料地址 http://www.ziqiangxuetang.com/django/django-install.html 官方文档 一&#xff1a; 1先下载Django源码包&#xff0c;下载地址https://www.djangoproject.com/download/ 然后下载自己想安装的版本 Django 1.5.x 支持 Python 2.6.5 Python 2.7, Python 3.2 和 3…

linux进程 网络占用率,linux CPU SI软中断比较占用率比较大(网络解决方案)

https://my.oschina.net/323148/blog/724408irq 默认linux自动启动的&#xff0c;但是往往它自己控制不是很好(CPU SI经常某个CPU占用大)通常碰到大流量的&#xff0c;通常我们会把自动启动的irqblance关闭&#xff0c;然后手动指定一下IRQ进行优化&#xff1a;看CPU的 si利用率…

android设备未指定怎么办,APKpath未指定为模块“示例 – 示例”

退出Android工作室 。 用pipe理员权限启动它。这解决了Windows 7中的 Android Studio v0.1的问题。我有同样的问题&#xff0c;我没有select 2个文件&#xff0c;然后收到错误"ERROR: APK path is not specified for module"我刚刚重新启动Android Studio并重新打开该…

链表 -- 双向循环链表(线性表)

1&#xff0c;双向链表也叫双链表&#xff0c;是链表的一种&#xff0c;它的每个数据结点中都有两个指针&#xff0c;分别指向直接后继和直接前驱。所以&#xff0c;从双向链表中的任意一个结点开始&#xff0c;都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循…

开发脚本自动部署及监控

1.编写脚本自动部署反向代理、web、nfs&#xff1b; 要求&#xff1a; I、部署nginx反向代理三个web服务&#xff0c;调度算法使用加权轮询&#xff1b; #!/bin/shngxStatusps aux | grep -v grep |grep -c nginxfunction ngxProxyInstall() { if [ -e /usr/sbin/nginx ];the…

服务器日志显示乱码,CentosOS 6.5 服务器 控制台输出中文乱码,日志打印中文也乱码...

系统是Centos 6.5使用localeLANGen_US.UTF-8LC_CTYPE"en_US.UTF-8"LC_NUMERICzh_CN.UTF-8LC_TIME"en_US.UTF-8"LC_COLLATE"en_US.UTF-8"LC_MONETARYzh_CN.UTF-8LC_MESSAGES"en_US.UTF-8"LC_PAPERzh_CN.UTF-8LC_NAMEzh_CN.UTF-8LC_ADDR…

go linux 源码编译环境,Linux 源码安装 GO 环境

Go 安装1.4以上的版本出现的问题个人在安装 go1.9.2 的时候&#xff0c;一直 提醒的错误是&#xff1a;Building Go bootstrap tool.cmd/distERROR: Cannot find /root/go1.4/bin/go.Set $GOROOT_BOOTSTRAP to a working Go tree > Go 1.4.步骤如果之前已经安装过老版本的 G…

django html数据库连接,Django数据库连接的问题

多线程运行项目。有N个工作线程从DB中获取jobs&#xff0c;并把结果写回DB。项目运行一段时间后&#xff0c;发现数据库连接耗尽了&#xff0c;幸好内存大&#xff0c;然后一直往上调&#xff0c;最后连接数都上8000多。耗尽连接数的时候&#xff0c;postgresql会出现类似这样的…

Java Web之XML基础

有好几天没有更新博客了&#xff0c;前段时间因为要开学了&#xff0c;需要凑足学费才能继续在学校学习&#xff0c;耽误了几天&#xff0c;这两天需要补充前面需要学习的一些知识点了。今天就开始进入JavaWeb阶段吧&#xff0c;这段时间我们需要了解一些前端的知识&#xff0c…

ios NSLayoutConstraint

为了让我们的应用在不同尺寸的屏幕下都能 “正常”的表示&#xff0c;我们尽量不要把数据写死。大多数可视元素都是一个矩形区域&#xff0c;当然这个矩形区域有坐标的&#xff0c;我们有了这个区域坐标就能确定可视元素的现实位置了。但是iphone5和以前的屏幕不一样了&#xf…

分布式技术追踪 2017年第十二期

分布式系统实践 1. 深入Facebook图数据库系统&#xff08;TAO&#xff09;系列 http://dwz.cn/5zQEdo http://dwz.cn/5zQEBK http://dwz.cn/5zQEPV 摘要: TAO是Facebook 的分布式图数据库, 存储了Facebook所有的社交关系数据, TAO的QPS超过30亿, 作者曾经在Facebook做过TAO相关…

linux 统计日志数量总,shell统计日志中时间段内匹配的数量的方法

shell统计日志中时间段内匹配的数量的方法&#xff0c;有需要的朋友可以参考下。假设日志文件mtasvr.log格式如下&#xff1a;T:24583088(04:02:06)[root:Info] 6KqowLDLAgC93DFIKrENAA.41S2:from,to, queuedT:122428336(13:36:51)[root:Info] 6KqowLAbAAByYzJIZGsOAA.2W:from,…

商品评论html,商品评论列表.html

提交取 消new Vue({el: #app,data: {fullLoad:,dialogVisible:false,jsonData:{"id":"","type":"edit","list":[{"type":"grid","icon":"icon-grid-","columns":[{"…

autolayout autoresizing

WWDC 2012 Session笔记——202, 228, 232 AutoLayout(自动布局)入门 这是博主的WWDC2012笔记系列中的一篇&#xff0c;完整的笔记列表可以参看这里。如果您是首次来到本站&#xff0c;也许您会有兴趣通过RSS&#xff0c;或者通过页面左侧的邮件订阅的方式订阅本站。 AutoLayout…

MongoDB安装和MongoChef可视化管理工具的使用

MongoDBWindows 用户向导&#xff1a;https://docs.mongodb.com/manual/tutorial/install-mongodb-on-windows/注意&#xff1a;最后一步时&#xff0c;左下角的勾勾要去掉&#xff0c;mongodb compass是图形化管理界面&#xff0c;下载它需要很久很久&#xff0c;还有可能一直…

angular轮播图

还是直接上代码比较好 <!doctype html><html lang"en"><head> <meta charset"UTF-8" /> <title>Document</title> <link rel"stylesheet" type"text/css" href"css/animate.min.css"…

linux 脚本的作用,shell export 作用

shell与export命令用户登录到Linux系统后&#xff0c;系统将启动一个用户shell。在这个shell中&#xff0c;可以使用shell命令或声明变量&#xff0c;也可以创建并运行shell脚本程序。运行shell脚本程序时&#xff0c;系统将创建一个子shell。此时&#xff0c;系统中将有两个sh…

标签选择器用于修改html元素默认的样式,html – 为什么CSS选择器与 sign(直接子)覆盖默认样式?...

问题不是子组合器(>)&#xff0c;它是color属性&#xff0c;它是可继承的。虽然颜色属性的初始值因浏览器而异&#xff0c;但继承是常见的。这意味着元素的文本颜色从父代继承。您在代码中看到这一点。相反&#xff0c;border属性是不可继承的。请注意&#xff0c;与文字颜色…

[hdu1828] Picture

帅哥美女们大家好&#xff01; 今天本蒟蒻补一篇题解&#xff01; 线段树维护扫描线求矩形周长并。 扫描线的话&#xff0c;跟求面积类似&#xff0c;这道题可以只扫一次&#xff0c;也可以x&#xff0c;y两个方向分别扫一次。 题目传送门 1 #include<cstdio>2 #include&…