luqiuyu

摘要： 省选D1T1 题意: 我们提出一个随机链剖分，指的是\(v_i\)是重儿子的概率为\(v_i\)的重链长度比上\(v_i\)的兄弟节点以及自己的重链长度，求期望之和 部分分 8分 特殊性质A 一条链，一眼瞪出答案为\(0\),全部输出\(0\)即可 40分 注意到\(ans=\sum_{i=2}^{ 阅读全文

摘要： Tarjan算法笔记 \(Tarjan\)算法得名与他的发明者:老头子\(Robert\)·\(Tarjan\)(\(1948\)-至今) \(Tarjan\)提出过许多图论算法，其中最有名的便是关于联通分量的算法:\(Tarjan\)算法 写作顺序为笔者学习顺序 无向图 我们先讨论无向图的联通分量 阅读全文

摘要： 分块 在我们讲分块前，我们先引入一个例题 区间加，区间和，\(1 \le n, q \le 10^5\) 若我们只是知道非懒标记线段树学过线段树肯定会,而且我们不知道树状数组这玩意或学过但想不出来的话，那么这道题只能望洋兴叹了。可我们也绝非闲人，若不会高级线段树，树状数组，那么我们便造一个可以过这道 阅读全文

摘要： 线段树 序 上次我们讲解了夹在数据结构和树论中的树链剖分现在我们将树链剖分的序列版本，实际上树链剖分是线段树的树版本俗话说，我们要想理解一个庞大的数据结构,那么我们需要将他的1.思想,2.实现,3.理解 第一步 思想 先给出例题 给你一个序列，有q次查询/修改，1.单点加 2.区间查询和,若n为序列 阅读全文

摘要： 树链剖分 序 我们知道，在序列上的算法有很多，比如应用广的线段树,可以解决简单问题的树状数组,有不带修改的RMQ问题ST等可树上的问题就很难解决了，因为树没有区间，那如果在u->v的简单路径上做一点操作，那岂不炸了于是有了树链剖分 第一步 思想 树链剖分，顾名思义，就是把数剖成一条一条链，然后用线段 阅读全文

摘要： 我的第一篇博客 阅读全文