Treap和名次树
Treap名字的来源：Tree+Heap，正如名字一样，就是一颗简单的BST，一坨堆的合体。BST的不平衡的根本原因在于基于左<=根<=右的模式吃单调序列时候会无脑成长链，而Treap则添加一个优先级属性，值的大小随机生成，用最大堆的方式维护。之所以使用堆，是因为堆是一颗 完全二叉树，而...
UVaLive5031 Graph and Queries（时光倒流+名次树）
题目链接：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=20332【思路】时光倒流+名次树（rank tree）。所谓“时光倒流”即逆向处理，因为D删除边并不好操作所以我们倒着处理，删除边转化为添加边，C转化为将weight变...
LA 5031 Graph and Queries —— Treap名次树
离线做法，逆序执行操作，那么原本的删除边的操作变为加入边的操作，用名次树维护每一个连通分量的名次，加边操作即是连通分量合并操作，每次将结点数小的子树向结点数大的子树合并，那么单次合并复杂度O(n1logn2)，由于合并之后原本结点数少的子树结点数至少翻倍，所以每个结点最多被插入 logn 次，故总时...
UVa 1479 (Treap 名次树) Graph and Queries
这题写起来真累。。名次树就是多了一个附加信息记录以该节点为根的树的总结点的个数，由于BST的性质再根据这个附加信息，我们可以很容易找到这棵树中第k大的值是多少。所以在这道题中用一棵名次树来维护一个连通分量。由于图中添边比较方便，用并查集来表示连通分量就好了，但是删边不太容易实现。所以，先把所有的边删...
LA 5031 Graph and Queries （【名次树(treap)】+【并查集】+【离线算法】）
题目链接：https://cn.vjudge.net/problem/UVALive-5031You are given an undirected graph with N vertexes and M edges. Every vertex in this graph has an intege...
LA 5031 Graph and Queries (离线处理 + Treap树维护名次)
【题目链接】http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=20332 【PS】算法入门经典Treap的例题，树上讲得非常仔细，在P234。再大致说一下这一个题，很经典。 【题意】给定无向图，有三种操作，①删除第i条边②查询节点...
LA 5031 Graph and Queries【名次树】【离线算法】
题目大义 有一张n结点m条边的无向图，每个结点都有一个权值，你的任务是执行一系列操作，共3种。 1、D X 删除ID为x的边 2、Q X k 计算与x相连的边的第k大权值，如果不存在输出0 3、C X V 把X的权值改为V 题目链接什么的还是给一个 https://icpcar...
【UVALive】5031 Graph and Queries treap实现名次树
传送门：【UVALive】5031 Graph and Queries 题目分析：第一道treap~yeah 代码如下： #include <cstdio>#include <cstdlib>#include <cstring>#include <a...
uvalive 5031 Graph and Queries 名次树+Treap
题意：给你个点m条边的无向图，每个节点都有一个整数权值。你的任务是执行一系列操作。操作分为3种。。。思路：本题一点要逆向来做，正向每次如果删边，复杂度太高。逆向到一定顺序的时候添加一条边更容易。详见算法指南P235。#include<cstdlib>structNode{Node*ch[...
UVaLive5031 Graph and Queries（时光倒流+名次树）
题目链接：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=20332 【思路】 时光倒流+名次树（ranktree）。 所谓“时光倒流”即逆向处理，因为D删除边并不好操作所以我们倒着处理，删除边转化为添加边...