#P7229. [2023省队模拟]上学

    ID: 7063 传统题 1000ms 25MiB 尝试: 5 已通过: 2 难度: 8 上传者: 标签>CF2400提高+/省选-离线查询深度优先搜索可撤销并查集按大小合并离散化根号分块

[2023省队模拟]上学

题目描述

给定一个有 nn 个顶点的图,每个顶点有一个点权,初始没有边。共有 mm 次操作。第 ii 次操作可能是以下三种之一。

  1. 1 x y:添加一条连接 xx 与 yy 的双向边,允许 x=yx=y。
  2. 2 x:回到第 xx 次操作完成后的状态。保证 x<ix<i。x=0x=0 表示回到初始状态。
  3. 3 x y:查询 xx 所在连通块中第 yy 小的点权。如果不存在,输出 −1-1。

输入格式

第一行两个整数 n,mn,m,分别表示顶点数和操作数。第二行 nn 个整数,依次表示各个顶点的点权。

接下来 mm 行,每行一个上述操作。

输出格式

对于每次类型为 33 的操作,输出一行一个整数表示答案。

样例输入

6 10
816801151 223885531 110182151 94271893 319888699 106363731
1 1 3
1 3 5
1 2 4
1 4 6
1 1 2
3 1 1
2 4
1 1 2
3 1 4
2 7

样例输出

94271893
223885531

数据范围与约定

对于所有数据,1≤n,m≤1051\le n,m\le10^5,输入的所有数在 int 范围内。

  • 子任务 1(20 分):n,m≤1000n,m\le1000。
  • 子任务 2(20 分):不存在类型为 22 的操作。
  • 子任务 3(60 分):空间小于 50MB50\mathrm{MB} 得本子任务 50%50\% 的分数,空间小于 25MB25\mathrm{MB} 得本子任务 100%100\% 的分数。