http://hzxjhs.com:83/contest/456
文章图片
果断可并堆
【数据结构|【NOI集训】【XJ】可持久化左偏树】
#include
#include
#include
#include
#include
#include
#define Rep(i, x, y) for (int i = x;
i <= y;
i ++)
#define RepE(i, x) for (int i = pos[x];
i;
i = g[i].nex)
#define p t[z]
#define u t[x]
#define v t[y]
using namespace std;
typedef long long LL;
const int N = 200005;
struct arr { int d, w, l, r;
} t[N * 100];
int n, q, a[N], sz, nz, ro[N];
int Merge(int x, int y) {
if (!x || !y) return x + y;
if (v.w > u.w) swap(x, y);
int z = ++ sz;
p = u;
p.r = Merge(p.r, y);
if (t[p.r].d > t[p.l].d) swap(p.r, p.l);
p.d = t[p.r].d + 1;
return z;
}
int newd(int y) { int x = ++ sz;
u.w = y;
return x;
}
int Qry(int x, int y) {
Rep(i, 1, y - 1) {
x = Merge(u.l, u.r);
}
return u.w;
}
int main()
{
scanf ("%d%d", &n, &q);
Rep(i, 1, n) scanf ("%d", &a[i]), ro[i] = newd(a[i]);
nz = n;
Rep(i, 1, q) {
int ty, x, y, z;
scanf ("%d", &ty);
if (ty == 1) {
scanf ("%d%d%d", &z, &x, &y);
ro[++ nz] = Merge(newd(z), Merge(ro[x], ro[y]));
// c1[nz] = x, c2[nz] = y;
} else if (ty == 2) {
scanf ("%d", &x);
// Merge()
} else {
scanf ("%d%d", &x, &y);
printf ("%d\n", Qry(ro[x], y));
}
}
return 0;
} 推荐阅读
- 笔记|C语言数据结构——二叉树的顺序存储和二叉树的遍历
- C语言学习(bit)|16.C语言进阶——深度剖析数据在内存中的存储
- 数据结构和算法|LeetCode 的正确使用方式
- 先序遍历 中序遍历 后序遍历 层序遍历
- 数据结构|C++技巧（用class类实现链表）
- 数据结构|贪吃蛇代码--c语言版 visual c++6.0打开
- 算法|算法-二分查找
- 数据结构学习指导|数据结构初阶（线性表）
- leetcode题解|leetcode#106. 从中序与后序遍历序列构造二叉树
- java|ObjectOrientedProgramming - 面向对象的编程（多态、抽象类、接口）- Java - 细节狂魔