Treap树经典题 [HDU3726] Graph and Queries

2024-04-13 03:08
文章标签 graph 经典 queries treap hdu3726

本文主要是介绍Treap树经典题 [HDU3726] Graph and Queries，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

模板：求第k小的key值 和 求数key是第k小的k值

struct Node {int size;int rank;int key;Node* lson, * rson;Node(int x) {lson = rson = NULL;rank = rand();key = x;size = 1;}
};
int getSize(Node* o) {if (o == NULL)return 0;return o->size;
}
void L_rotate(Node*& o) {Node* k = o->rson;o->rson = k->lson;k->lson = o;k->size = o->size;o->size = getSize(o->lson) + getSize(o->rson) + 1;o = k;
}
void R_rotate(Node*& o) {Node* k = o->lson;o->lson = k->rson;k->rson = o;k->size = o->size;o->size = getSize(o->lson) + getSize(o->rson) + 1;o = k;
}
void insert(Node*& o, int x) {if (o == NULL) o = new Node(x);else {o->size++;if (o->key < x) {insert(o->rson, x);if (o->rank < o->rson->rank)L_rotate(o);}else {insert(o->lson, x);if (o->rank < o->lson->rank)R_rotate(o);}}
}
int kth(Node* o, int k) {if (o == NULL)return -1;int temp = getSize(o->lson) + 1;if (temp == k)return o->key;if (temp > k)return kth(o->lson, k);return kth(o->rson, k - temp);
}
int find(Node* o, int key) {if (o == NULL)return -1;if (o->key == key)return o->lson == NULL ? 1 : o->lson->size + 1;if (o->key > key)return find(o->lson, key);int temp = find(o->rson, key);if (temp == -1)return -1;return o->lson == NULL ? temp + 1 : temp + o->lson->size + 1;
}
void remove(Node*& o) {if (o == NULL)return;Node* temp = o;if (o->lson == NULL) { o = o->rson; delete temp; }else if (o->rson == NULL) { o = o->lson; delete temp; }else {if (o->lson->rank > o->rson->rank) {R_rotate(o); remove(o->rson);}else {L_rotate(o); remove(o->lson);}}
}
void merge(Node* a, Node* b) {if (b->lson != NULL)merge(a, b->lson);if (b->rson != NULL)merge(a, b->rson);insert(a, b->key); delete b; b = NULL;
}

还有第二种模板，修改起来方便，但是更慢一点，如下：

struct Node{int size;int rank;int key;Node* son[2];bool operator < (const Node& a) const { return rank < a.rank; }int cmp(int x)const {if (x == key)return -1;return x < key ? 0 : 1;}void update() {size = 1;if (son[0] != NULL)size += son[0]->size;if (son[1] != NULL)size += son[1]->size;}
};
void rotate(Node*& o, int d) { // d=0,左旋;d=1,右旋Node* k = o->son[d ^ 1];o->son[d ^ 1] = k->son[d];k->son[d] = o;o->update();k->update();o = k;
}
void insert(Node*& o, int x) {if (o == NULL) {o = new Node();o->son[0] = o->son[1] = NULL;o->rank = rand();o->key = x;o->size = 1;}else {int d = o->cmp(x);insert(o->son[d], x);o->update();if (o < o->son[d])rotate(o, d ^ 1);}
}
int kth(Node* o, int k) {if (o == NULL || k <= 0 || k > o->size)return -1;int s = o->son[1] == NULL ? 0 : o->son[1]->size;if (k == s + 1)return o->key;else if (k <= s)return kth(o->son[1], k);else return kth(o->son[0], k - s - 1);
}
int find(Node* o, int k) {if (o == NULL)return -1;int d = o->cmp(k);if (d == -1)return o->son[1] == NULL ? 1 : o->son[1]->size + 1;else if (d == 1)return find(o->son[d], k);else {int tmp = find(o->son[d], k);if (tmp == -1)return -1;elsereturn o->son[1] == NULL ? tmp + 1 : tmp + 1 + o->son[1]->size;}
}
void del_tree(Node*& a) {if (a->son[0])del_tree(a->son[0]);if (a->son[1])del_tree(a->son[1]);delete a; a = NULL;
}

题目链接：[HDU3726] Graph and Queries

知识点：Treap树+并查集+离线逆序操作+启发式合并

搞来搞去发现最后是Treap树的remove操作写错了…抄了一下别人的remove

#include<cstdio>
#include<cstdlib>
#include<ctime>
using namespace std;
const int maxn = 2e4 + 5;
const int maxm = 6e4 + 5;
const int maxc = 6e5 + 5;
struct edge {int u, v;
}e[maxm];
struct CMD {int ch[5], x, k;
}cmd[maxc];
int fa[maxn], val[maxn], vis[maxm];
int n, m, kase;
struct Node{Node* son[2];int rank, key, size, id;void update(){size = 1;if (son[0] != NULL) size += son[0]->size;if (son[1] != NULL) size += son[1]->size;}
};
Node* root[maxn];
int findfa(int x){return (x == fa[x]) ? x : fa[x] = findfa(fa[x]); 
}
inline void rotate(Node*& o, int d) {Node* k = o->son[d ^ 1];o->son[d ^ 1] = k->son[d];k->son[d] = o; o = k;k->son[d]->update();k->update();
}
void insert(Node*& o, int x, int id) {if (o == NULL) { o = new Node(); o->son[0] = o->son[1] = NULL; o->key = x; o->rank = rand(); o->id = id; }else{int d = (x < o->key || (x == o->key && id < o->id)) ? 0 : 1;insert(o->son[d], x, id);if (o->son[d]->rank > o->rank) rotate(o, d ^ 1);}o->update();
}
void remove(Node*& o, int x, int id){if (o == NULL) return;int d = ((x < o->key || (x == o->key && id < o->id)) ? 0 : 1);if (o->key == x && id == o->id){Node* tmp = o;if (o->son[0] == NULL) { o = o->son[1]; delete tmp; }else if (o->son[1] == NULL) { o = o->son[0]; delete tmp; }else{int d2 = (o->son[0]->rank > o->son[1]->rank) ? 1 : 0;rotate(o, d2); remove(o->son[d2], x, id);}}else remove(o->son[d], x, id);if (o != NULL) o->update();
}
int kth(Node* o, int k) {if (o == NULL || k <= 0 || k > o->size)return 0;int s = o->son[1] == NULL ? 0 : o->son[1]->size;if (k == s + 1)return o->key;else if (k <= s)return kth(o->son[1], k);else return kth(o->son[0], k - s - 1);
}
void merge(int id, Node*& a, Node*& b) {if (b->son[0] != NULL) merge(id, a, b->son[0]);if (b->son[1] != NULL) merge(id, a, b->son[1]);fa[b->id] = id; insert(a, b->key, b->id); delete b; b = NULL;
}
int main(void) {while (~scanf("%d %d", &n, &m) && n && m) {for (int i = 1; i <= n; ++i) scanf("%d", &val[i]);for (int i = 1; i <= m; ++i) {scanf("%d %d", &e[i].u, &e[i].v);vis[i] = 0;}char s[10]; int tot = 0;for (;; tot++) {scanf("%s", cmd[tot].ch);if (cmd[tot].ch[0] == 'E') break;if (cmd[tot].ch[0] == 'D') {scanf("%d", &cmd[tot].x);vis[cmd[tot].x] = 1;}elsescanf("%d %d", &cmd[tot].x, &cmd[tot].k);if (cmd[tot].ch[0] == 'C') {int x = cmd[tot].x, v = cmd[tot].k;cmd[tot].k = val[x];val[x] = v;}}for (int i = 1; i <= n; ++i) { root[i] = NULL; insert(root[i], val[i], i); fa[i] = i; }for (int i = 1; i <= m; ++i) {if (vis[i])continue;int tmpa = findfa(e[i].u), tmpb = findfa(e[i].v);if (tmpa == tmpb) continue;if (root[tmpa]->size > root[tmpb]->size) merge(tmpa, root[tmpa], root[tmpb]);else merge(tmpb, root[tmpb], root[tmpa]);}double ans = 0, cnt = 0;for (int i = tot - 1; i >= 0; --i) {if (cmd[i].ch[0] == 'D') {int fa1 = findfa(e[cmd[i].x].u), fa2 = findfa(e[cmd[i].x].v);if (fa1 == fa2) continue;if (root[fa1]->size > root[fa2]->size)merge(fa1, root[fa1], root[fa2]);elsemerge(fa2, root[fa2], root[fa1]);}else if (cmd[i].ch[0] == 'Q') {cnt++;ans += kth(root[findfa(cmd[i].x)], cmd[i].k);}else {int rt = findfa(cmd[i].x);remove(root[rt], val[cmd[i].x], cmd[i].x);insert(root[rt], cmd[i].k, cmd[i].x);val[cmd[i].x] = cmd[i].k;}}if (cnt == 0)cnt++;printf("Case %d: %.6lf\n", ++kase, ans / cnt);}return 0;
}

右转Splay树的题解(第三题)：https://blog.csdn.net/TK_wang_/article/details/108751229

这篇关于Treap树经典题 [HDU3726] Graph and Queries的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/898977。

相关文章

HotSpot虚拟机的经典垃圾收集器

HotSpot虚拟机的经典垃圾收集器

读《深入理解Java虚拟机》第三版笔记。 关系 Serial、ParNew、Parallel Scavenge、Parallel Old、Serial Old(MSC)、Concurrent Mark Sweep (CMS)、Garbage First(G1)收集器。 如图： 1、Serial 和 Serial Old 收集器 2、ParNew 收集器 3、Parallel Sc
阅读更多...
STL经典案例（四）——实验室预约综合管理系统（项目涉及知识点很全面，内容有点多，耐心看完会有收获的！）

STL经典案例（四）——实验室预约综合管理系统（项目涉及知识点很全面，内容有点多，耐心看完会有收获的！）

项目干货满满，内容有点过多，看起来可能会有点卡。系统提示读完超过俩小时，建议分多篇发布，我觉得分篇就不完整了，失去了这个项目的灵魂 一、需求分析 高校实验室预约管理系统包括三种不同身份：管理员、实验室教师、学生 管理员：给学生和实验室教师创建账号并分发 实验室教师：审核学生的预约申请 学生：申请使用实验室 高校实验室包括：超景深实验室（可容纳10人）、大数据实验室（可容纳20人）、物联网实验
阅读更多...
图神经网络框架DGL实现Graph Attention Network (GAT)笔记

图神经网络框架DGL实现Graph Attention Network (GAT)笔记

参考列表： [1]深入理解图注意力机制 [2]DGL官方学习教程一 ——基础操作&消息传递 [3]Cora数据集介绍+python读取 一、DGL实现GAT分类机器学习论文 程序摘自[1]，该程序实现了利用图神经网络框架——DGL，实现图注意网络（GAT）。应用demo为对机器学习论文数据集——Cora，对论文所属类别进行分类。（下图摘自[3]） 1. 程序 Ubuntu：18.04
阅读更多...
嵌入式面试经典30问：二

嵌入式面试经典30问：二

1. 嵌入式系统中，如何选择合适的微控制器或微处理器？ 在嵌入式系统中选择合适的微控制器（MCU）或微处理器（MPU）时，需要考虑多个因素以确保所选组件能够满足项目的具体需求。以下是一些关键步骤和考虑因素： 1.1 确定项目需求 性能要求：根据项目的复杂度、处理速度和数据吞吐量等要求，确定所需的处理器性能。功耗：评估系统的功耗需求，选择低功耗的MCU或MPU以延长电池寿命或减少能源消耗。成本
阅读更多...
Leetcode面试经典150题-128.最长连续序列-递归版本另解

Leetcode面试经典150题-128.最长连续序列-递归版本另解

之前写过一篇这个题的，但是可能代码比较复杂，这回来个简洁版的，这个是递归版本 可以看看之前的版本，两个版本面试用哪个都保过 解法都在代码里，不懂就留言或者私信 class Solution {/**对于之前的解法，我现在提供一共更优的解，但是这种可能会比较难懂一些（思想方面）代码其实是很简洁的，总体思想如下：不需要排序直接把所有数放入map，map的key是当前数字，value是当前数开始的
阅读更多...
力扣 739. 每日温度【经典单调栈题目】

力扣 739. 每日温度【经典单调栈题目】

1. 题目 理解题意： 1.1. 给一个温度集合， 要返回一个对应长度的结果集合， 这个结果集合里面的元素 i 是 当前 i 位置的元素的下一个更高温度的元素的位置和当前 i 位置的距离之差， 若是当前元素不存在下一个更高温度的元素， 则这个位置用0代替； 2. 思路 本题用单调栈来求解；单调栈就适用于来求当前元素左边或者右边第一个比当前元素大或者小的元素；【单调栈：让栈中的元素保持单调
阅读更多...
SIGMOD-24概览Part7: Industry Session (Graph Data Management)

SIGMOD-24概览Part7: Industry Session (Graph Data Management)

👇BG3: A Cost Effective and I/O Efficient Graph Database in ByteDance 🏛机构：字节 ➡️领域： Information systems → Data management systemsStorage management 📚摘要：介绍了字节新提出的ByteGraph 3.0(BG3)模型，用来处理大规模图结构数据 背景
阅读更多...
接口自动化三大经典难题

接口自动化三大经典难题

目录 一、接口项目不生成token怎么解决关联问题 1. Session机制 2. 基于IP或设备ID的绑定 3. 使用OAuth或第三方认证 4. 利用隐式传递的参数 5. 基于时间戳的签名验证 二、接口测试中网络问题导致无法通过怎么办 1. 重试机制 2. 设置超时时间 3. 使用模拟数据 4. 网络问题的预检测 5. 日志记录与错误分析 6. 切换网络环境 7.
阅读更多...
嵌入式面试经典30问：一

嵌入式面试经典30问：一

什么是嵌入式系统？ 嵌入式系统是指嵌入到某个对象体系中的专用计算机系统，它负责执行特定的任务，具有专用性、隐蔽性、资源受限和可靠性要求高等特点。通常包括硬件和软件两部分，硬件以微处理器为核心，软件则负责控制和管理硬件资源，实现特定的应用功能。 嵌入式系统和普通计算机系统有什么区别？ 嵌入式系统与普通计算机系统的主要区别在于目的、资源、性能和成本等方面。嵌入式系统通常针对特定应用设计，具有体积小
阅读更多...
FHQ Treap模版（luogu P3369）

FHQ Treap模版（luogu P3369）

FHQ Treap模版（自用），带注释 #include<bits/stdc++.h>using namespace std;const int N=1e5+10;int n,root,idx;struct node{int l,r;int val,key,size;}tr[N];int getnew(int v){tr[++idx].val=v;//权值tr[idx].key=rand(
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2