xixike

# 问题引入 给一些操作，只在 l∼rl \sim rl∼r 时间段内有效。 给一些询问，查询在某一时间内所有操作的贡献。 # 主要思想 我们可以把操作和询问都离线下来，然后对于时间轴建一棵线段树。 对于操作，相当于是在线段树上进行区间修改；对于查询，不停地向下递归，统计答案，回溯时撤销掉操作。 这样的思想被称之为线段树分治。 # 例题 P5787 二分图 /【模板】线段树分治 # Solution 出现二分图的条件是不存在奇环，可以使用扩展域并查集维护。 再来看如何建树，我们先按照时间轴分区间，然后对于每个点开一个 vector ，对于每个操作所在的区间，往线段树上对应的节点的...

# 树链剖分（重链剖分） 模板：洛谷 P3384 【模板】轻重链剖分 / 树链剖分 写在前面：强烈建议初学的同学如果不理解的话先手写一遍（像我一样），非常有助于理解 # 概念： 重儿子： 一个节点所有儿子中最大的儿子 轻儿子： 一个节点除重儿子之外的其他儿子 特别地，叶子节点既没有重儿子也没有轻儿子 重链： 重儿子连接形成的链叫重链 # 主要思想： 把一颗树拆成许多条链，把树上操作改为链上操作（区间操作），并利用线段树或树状数组等数据结构维护，以降低时间复杂度 每次进行操作时，先修改重链，再修改轻链 # 常见操作： 将树从 xxx 到 yyy 结点最短路径上所有节点的值都加上...

# 前置芝士 重链剖分（最好是熟练掌握） 莫队（大概了解即可，有一点相似的思想） dfs 序（可有可无，主要是为了加速，其实我就没写过 QwQQwQQwQ） # 主要思想 dsu on treedsu\ on\ treedsu on tree 又名树上启发式合并 （其实是非常暴力的一个东西。） # 用途 可处理树上的一些统计类型的问题。 如： 求子树中颜色最多的颜色编号之和，相同数量都要加上 CF600E Lomsat gelral 给一棵树，树上每个节点都有一个颜色，求已点 uuu 为根的子树中，出现次数 >=k>= k>=k...

# 前言 模拟赛上考了一道反悔贪心，然而根本不会，于是蒟蒻就学习了一下。 # 概念 顾名思义，反悔贪心是反悔 + 贪心。 贪心一般来讲是没有撤销操作的，因为你贪心就是要贪最优解，哪里来的撤销呢？ 但是有的时候你贪心出来的 “最优解”...

# 浅谈 fhq-treap（无旋 treap） 模板题：洛谷 P6136 【模板】普通平衡树（数据加强版） （emm 刚写了这个，就放这个吧） fhq−treapfhq-treapfhq−treap 也叫做 无旋 treap，由范浩强大佬发明。 个人认为是平衡树中码量最少，也最容易理解的一种写法。 # 主要思想 顾名思义，无旋意味着它没有旋转操作（终于没有恶心人的旋转了）。 事实上，无旋 treap 只有两种操作。 一种是 splitsplitsplit（分裂），另一种是 mergemergemerge（合并）。 平衡树中的各种操作都可以用这两个函数来搞定。下面我们来一一分析。 #...

# 前言 说是学习笔记，其实窝并没有打算写太多（太麻烦了，而且我的理解还不是特别深，可能也写不清楚），所以打算大概写两句，然后贴个板子。 # 前置知识 Miller−RabinMiller-RabinMiller−Rabin 素性测试。 倍增基础应用。 # Miller−RabinMiller-RabinMiller−Rabin 素性测试 我们知道有费马小定理： ap−1≡1(modp)a^{p - 1} \equiv 1\pmod pap−1≡1(modp)，ppp 是质数且 aaa 是小于 ppp...

虽然很久之前学过一遍，但是又忘了 QwQ，于是重新复习了一遍。 CDQ 分治是一个离线算法，也只能用于离线问题的处理上。 # 主要思想 把当前区间分成两半，向下递归处理。 左边和右边独立的贡献计算出来之后，再计算左边对右边的贡献。 通常会套上一些树状数组之类的数据结构（不然和暴力有啥区别 QwQ） # 例题 板子题：P3810 【模板】三维偏序（陌上花开） # Solution 先按第一维从小到大排序，对于区间 (l,r)(l, r)(l,r)，递归处理 (l,mid)(l, mid)(l,mid) 和 (mid+1,r)(mid + 1, r)(mid+1,r)。 由于已经按照 aaa...

不打算详细写了，强推一波 yyb 神仙的博客 Splay 入门解析【保证让你看不懂（滑稽）】 （这篇博客的代码完全是按照 yyb 的博客写的，并有一些补充，包括 pushup 及查询第 k 大的整数等等） 这里列几个注意事项吧： SplaySplaySplay 过程中，如果 x,yx, yx,y 为同一种儿子，那么先旋转 yyy，再转 xxx，否则旋转两次 xxx。 rotate 时的顺序： 先改 zzz 的儿子（zzz 的儿子从 yyy 变成 xxx） xxx 的儿子中变动的那个儿子（从 xxx 的儿子变成 yyy 的儿子，至于是哪个建议背过，背不过的话现推一下规律） 最后令 yyy...

主席树的最基础的操作就是查询历史版本区间第 kkk 大，带修。 这个问题的基础解决思路：对于每次修改都建一棵权值线段树，显然空间开不下。 这时可持久化线段树的思路就应运而生了。 主要思想： 不难发现，每次修改只会有一条链上的值发生改变，所以我们不需要建出整棵新树，只需要把新建那条链上的点即可。 所以空间就是 nlog⁡nn\log nnlogn 的。 我们还要在权值线段树上做个前缀和来方便查询，每次查询时，就是在权值线段树上二分的过程。 注意到我们要建的是权值线段树，所以要对输入的值做一个离散化。 不多说了，直接贴代码吧。 code:code:code: mark#include...

# Day -2 大晚上的在机房颓废时，教练突然进来。 曰：“现在疫情又有反复，大家把核酸证明什么的都上传好，去秦皇岛也带上，多带点口罩和酒精湿巾，在火车上一直戴着口罩，向 fzj 学习，口罩不离嘴。” stostosto 房神 orzorzorz，真・防疫好少年。 然后教练继续曰：“到时候还要查健康码，大家能带手机的都带上。” 都…… 带…… 上……（为什么其他学校都是不让带手机，到了我们这里变成了强制带手机……） 没手机的咋办？感觉要凉凉，CSP RP−−CSP \...