第一次写路径加/乘的lct,多存了两个lazytag。 题目描述 一棵$ n$个点的树,每个点的初始权值为$ 1$。对于这棵树有$ q$个操作,每个操作为以下四种操作之一: + u v c:将$ u$到$ v$的路径上的...
splay
洛谷 P4180 [BJWC2010] 次小生成树 题解【LCT】【生成树】
这个题LCT做还是麻烦了一点…… 题目描述 小C最近学了很多最小生成树的算法,Prim算法、Kurskal算法、消圈算法等等。正当小C洋洋得意之时,小P又来泼小C冷水了。小P说,让小C求出一个无向图的次小生成树,...
SPOJ 913 QTREE2 – Query on a tree II 题解【LCT】【splay】
稍微利用了splay技巧的一道lct题目。 Description You are given a tree (an undirected acyclic connected graph) with N nodes, and edges numbered 1, 2, 3...N-1. Each edge has an integer value a...
SPOJ 913 QTREE2 – Query on a tree II 题解【LCT】【splay】
稍微利用了splay技巧的一道lct题目。 Description You are given a tree (an undirected acyclic connected graph) with N nodes, and edges numbered 1, 2, 3...N-1. Each edge has an integer value a...
洛谷 P3960 NOIp2017提高组 列队 题解【splay】【模拟】
领教了splay的强大/考场上只拿了无脑30分 【问题描述】 Sylvia 是一个热爱学习的女孩子。 前段时间,Sylvia参加了学校的军训。众所周知,军训的时候需要站方阵。 Sylvia所在的...
洛谷 P1486 [NOI2004]郁闷的出纳员 题解【平衡树】
带lazy的平衡树; 题目描述 OIER公司是一家大型专业化软件公司,有着数以万计的员工。作为一名出纳员,我的任务之一便是统计每位员工的工资。这本来是一份不错的工作,但是令人郁闷...
洛谷 P1377 [TJOI2011]树的序 暴力数据结构做法 题解【树的遍历】【splay】
这个题正解不是平衡树,不过可以拿平衡树优化一下常数,$ O(NlogN)$就能过了。 题目描述 众所周知,二叉查找树的形态和键值的插入顺序密切相关。准确的讲:1、空树中加入一个键值k,...
洛谷 P1110 [ZJOI2007]报表统计 题解【splay】【set】
一道splay的正常题,不过因为考试的时候一句话读错了于是开了2 splay +1 set 棵平衡树。。。事实上为了卡过这道题用1 splay + 1 set 是可以过洛谷神鸡的。 题目描述 小Q的妈妈是一个...
splay学习笔记3 文艺平衡树(伪解题报告)【splay】【平衡树】
摸鱼思考了一上午并调了下午两节课终于出来了。 首先,区间翻转用splay来做真的是不二选择,感觉现在已经把splay磨得差不多了。这个题其实就是像线段树一样打上lazy-tag来控制时间复杂度的思想...
splay学习笔记2 双旋splay+二进制优化【splay】【平衡树】
在网上找了一下,发现很多人都没有存父节点指针,今天实现了一下,感觉确实简洁许多。 不存父指针,有一个关键操作就是赋值,这一操作可以用=号来实现,也可以在函数调用时取址,直接更改,这里...