[Solution]
It's said that it's a very classic problem, although I don't know what the correct solution is.
My solution is to use treap to take the place of vector to make it persistent.
[Code]
Very ugly...
#include <cstdio>
#include <cstdlib>
#include <memory.h>
#include <algorithm>
using namespace std;
#ifdef WIN32
#define getRand() ((rand() << 16) | rand())
#else
#define getRand() rand()
#endif
const int maxa = 20009;
const int maxn = maxa * 40;
int n, m, ls[maxn], rs[maxn], sz[maxn], vl[maxn], w[maxn], rt[maxa], tn;
int newNode(int v0) {
int p = ++ tn;
ls[p] = 0;
rs[p] = 0;
sz[p] = 1;
vl[p] = v0;
w[p] = getRand();
return p;
}
inline void update(const int& x) {
sz[x] = sz[ls[x]] + sz[rs[x]] + 1;
}
int merge(int p, int q) {
if (!p)
return q;
else if (!q)
return p;
else if (w[p] > w[q]) {
rs[p] = merge(rs[p], q);
update(p);
return p;
}
else {
ls[q] = merge(p, ls[q]);
update(q);
return q;
}
}
int valOn(int p, int p0) {
if (sz[ls[p]] + 1 == p0)
return vl[p];
else if (sz[ls[p]] >= p0)
return valOn(ls[p], p0);
else
return valOn(rs[p], p0 - sz[ls[p]] - 1);
}
int changeNew(int p, int p0, int v0) {
int q = ++ tn;
vl[q] = vl[p];
ls[q] = ls[p];
rs[q] = rs[p];
sz[q] = sz[p];
if (sz[ls[p]] + 1 == p0)
vl[q] = v0;
else if (sz[ls[p]] >= p0)
ls[q] = changeNew(ls[p], p0, v0);
else
rs[q] = changeNew(rs[p], p0 - sz[ls[p]] - 1, v0);
update(q);
return q;
}
int getRoot(int c, int x) {
int r0 = valOn(rt[c], x);
if (r0 == x)
return r0;
else {
int rx = getRoot(c, r0);
return rx;
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("o1.txt", "w", stdout);
#endif
srand(12093409);
scanf("%d%d", &n, &m);
tn = 0;
rt[0] = 0;
for (int i = 1; i <= n; i ++)
rt[0] = merge(rt[0], newNode(i));
for (int i = 0; i < m; i ++) {
int opt, x, y;
scanf("%d", &opt);
if (opt == 1) {
scanf("%d%d", &x, &y);
x = getRoot(i, x);
y = getRoot(i, y);
if (rand() & 1)
rt[i + 1] = changeNew(rt[i], x, y);
else
rt[i + 1] = changeNew(rt[i], y, x);
}
else if (opt == 2) {
int k;
scanf("%d", &k);
rt[i + 1] = rt[k];
}
else if (opt == 3) {
int x, y;
scanf("%d%d", &x, &y);
x = getRoot(i, x);
y = getRoot(i, y);
if (x == y)
printf("1\n");
else
printf("0\n");
rt[i + 1] = rt[i];
}
}
}
文章浏览阅读1.5k次，点赞13次，收藏36次。文章目录一、快速幂快速幂模版（迭代，非递归）快速幂模版（递归）AcWing 875. 快速幂LeetCode 50. Pow(x, n)（快速幂 C++）LeetCode 372. 超级次方二、矩阵快速幂矩阵快速幂模版例题：求斐波那契数列的第 1e9 项例题： S=A+A2+A3+…+AkS = A + A^2 + A^3 + … + A^kS=A+A2+A3+…+AkREFERENCES一、快速幂快速幂：快速计算某个数的幂次( ana^nan )快速幂时间复杂度为 O(logn)O(logn)O(l_csdn 快速幂 矩阵快速幂 快速乘
文章浏览阅读632次，点赞12次，收藏13次。他们使用Wireshark等工具对网络流量进行实时监控和分析，以识别恶意行为和潜在的安全威胁。通过使用Wireshark等工具进行网络流量分析和攻击检测，阿里工作中的网络安全团队能够及时发现并应对各种潜在的安全威胁，保障公司的网络安全和数据安全。以上是使用Wireshark进行网络数据包分析，识别爬虫攻击行为的一个基本工作流程。在阿里工作的一个可能的应用场景是网络安全团队使用Wireshark进行网络流量分析和攻击检测。使用Wireshark进行网络数据包分析可以帮助识别网络中的各种行为，包括爬虫攻击。
文章浏览阅读503次。从第一个拿蛋糕的人开始枚举，每一轮迭代表示一个人拿蛋糕的过程（不论这个人是否能拿到>=k的蛋糕，他一定会拿到蛋糕，所以能拿到蛋糕的同学数量+1）根据累计这个人拿蛋糕的分量是否>=k，决定得到的蛋糕数量。每一轮迭代开始时，i都指向下一块即将分配的蛋糕。_code 一人拿一块蛋糕
文章浏览阅读948次，点赞21次，收藏23次。基于LLM的智能体因其决策能力和处理复杂任务的能力而备受关注。鉴于目前在推荐系统中利用智能体协作能力的空白，我们引入了MACRec，这是一个旨在通过多智能体协作增强推荐系统的新颖框架。与现有关于使用智能体进行用户/物品模拟的工作不同，我们旨在部署多智能体直接处理推荐任务。在我们的框架中，推荐任务通过各种专业智能体的协作努力来解决，包括经理用户/物品分析员反射器搜索器和任务解释器，具有不同的工作流程。
文章浏览阅读482次。磁场传感器在物联网应用中扮演着重要的角色，它们可以帮助我们检测和测量周围环境中的磁场。在本篇文章中，我们将使用ESP8266和Arduino编程来驱动MLX90393磁场传感器。通过连接和编程，我们可以轻松地读取和解析传感器数据，从而在物联网应用中实现精确的磁场测量和控制。将ESP8266的GND引脚连接到MLX90393传感器的GND引脚。将ESP8266的D1引脚连接到MLX90393传感器的SDA引脚。将ESP8266的D2引脚连接到MLX90393传感器的SCL引脚。如果有数据可用，我们将使用。_arduino 90393代码
文章浏览阅读8.8k次。NVMe（非易失性存储器快速）是一种主机控制器接口和存储协议，用于通过计算机的高速外围组件互连高速（PCIe）加速企业和客户端系统与固态硬盘（SSD）之间的数据传输总线。NVMe 规范定义了基于 PCIe 的 SSD 的寄存器接口，命令集和功能集合，其目标是在各种 NVM 子系统中实现高性能和互操作性。NVMe 规范没有规定最终使用模型，例如固态存储，主存储器，高速缓冲存储器或备份存储器。NVMe 提供了小型计算机系统接口（SCSI）标准和高级技术附件（ATA）标准的替代方案，用于在主机系统和外_nvme接口定义
文章浏览阅读9.7k次，点赞4次，收藏24次。借鉴博客 https://www.51halcon.com/thread-387-1-1.html1.下载HALCON官网下载地址 https://www.mvtec.com/download/halcon/找了很多教程，终于成功安装好HALCON了，在这里该大家分享一下过程，亲测有效。按照上图中标记选择下载，下载过程应该是需要注册一个邮箱，注册就好。2.安装下载完就可以直接安装..._halcon19.11 x86下载
文章浏览阅读52次。下载地址：http://www.fishlee.net/soft/ilspy_chs/转载于:https://www.cnblogs.com/dengxixi/p/9327727.html
文章浏览阅读2.6k次。序列化就是将python中的字典转换为一种特殊的字符串（json）那么反序列化就是，将json字符串转换为python字典想输出真正的中文需要指定ensure_ascii=False,还可以使用排序sort_keys,缩进:indentprint(json.dumps({'a':'str', 'c': True, 'e': 10, 'b': 11.1, 'd': None, 'f': [1, 2, 3], 'g':(4, 5, 6)}, sort_keys=True, indent=4)) jso_python json序列化和反序列化
文章浏览阅读1.3k次，点赞30次，收藏24次。BootLoader（引导加载程序）是一种软件，它负责在计算机系统启动时加载操作系统或其他应用程序。BootLoader通常是存储在计算机系统的非易失性存储器中（如固态硬盘、闪存等），并在系统上电时自动执行。BootLoader通常由计算机制造商或操作系统开发商提供，但也有一些独立的BootLoader可用于多个操作系统的引导管理。_bootloader
文章浏览阅读1k次。《采用晶体管作为电子元器件的计算机属于(》由会员分享，可在线阅读，更多相关《采用晶体管作为电子元器件的计算机属于((20页珍藏版)》请在技术文库上搜索。1、袋惰掂志昼诌脓窥造分每痔瑟街谢炮里雪猾邑剑也郎笑罪陨双玛般搐脚绵噶衡辜隧召固玛驳患迄惊约茎持钻葫挪枝冬锈釜茅英级甚韦性极傈讲斧蝎交占玄帛麦凸蕊缆万元驳待荫刹宪茅荒拓常擂奄迄笑呢泣铝蜂爆耳历襟撅枯锥愁恒梁和时俄睛阮翻哉桔廉韧见瑰票彻逆替憎轮慢馅羌..._用晶体管作为电子器件制成的计算机属于( )。
文章浏览阅读379次，点赞4次，收藏5次。所有现代浏览器都内置了屏蔽弹窗的程序，因此大多数意料之外的弹窗都会被屏蔽。在浏览器屏蔽 弹窗时，可能会发生一些事。如果浏览器内置的弹窗屏蔽程序阻止了弹窗，那么 window.open()很可 能会返回 null。在浏览器扩展或其他程序屏蔽弹窗时，window.open()通常会抛出错误。