【算法介绍】树上莫队
算法简介：重帘留香树上莫队，就是字面意思上的树上的莫队，但实际上，一般来讲的树上莫队指的都是用欧拉序把一棵树压成数组，然后对其进行普通莫队的操作。
算法演示：天青现虹算法推导：织诗成锦那么首先我们可以随便画一棵树
然后我们首先手动算一算他的欧拉序。应该是 $[1,2,4,5,5,6,6,7,7,4,2,3,3,1]$ 。
那么我们考虑如果我们需要查询一个路径 $5-4-2-1-3$ ，会发生什么事。那么首先把他转化成欧拉序上的一段，也就是 5 的最后一次出现位置，和 3 的第一次出现位置，那么把它所对应的那一段截取下来就应该是：$[5,6,6,7,7,4,2,3$] ，观察，我们发现这个路径上的点，在这段内容中，多了 6 和 7 但是他们出现次数都是偶数，不难想到用异或或者 vis 去重可以得到，其次是 1 号点，1 号点是 LCA 我们应该需要特殊计算。所以说大概的找找规律，可以知道大概的计算方式。接着就是按照这样的规则模拟即可。
最后有一个细节问题，欧拉序的大小是原来的两倍！
例题讲解：孤舟斩蛟这里提供一道非常非常模板的题目：SP10707
就是在上述板子的基础上统计一波颜色即可 ...
【拾题杂谈】CF1166F - Vicky's Delivery Service
题面题面翻译有 $n$ 个点，$m$ 条边的图，每条边有一种颜色。定义一条路（经过的点是 $c_1,c_2,\dots,c_k$）是彩虹路，要求满足 $2$ 个条件：
对于所有 $1 \le i \le k - 1$，$c_i$ 和 $c_{i+1}$ 有边。
对于所有 $1 \le i \le \dfrac{k-1}{2}$，$c_{2i}$ 和 $c_{2i-1}$ 的边的颜色与 $c_{2i}$ 和 $c_{2i+1}$ 的边的颜色相同。
现在有 $q$ 次操作：
x y z：向点 $x$ 和 $y$ 之间建一条颜色为 $z$ 的边。
? x y：询问 $x$ 点和 $y$ 点之间是否有彩虹路。
思路我们首先可以想到 对于点 xx，它连出去的同种颜色连着的点都是可以相互到达的，所以我们可以将它们用并查集合并。我们要快速查询一个点连出去某种颜色的边，这里用了一个 map 。这样我们就处理完了走偶数步的情况，对于走奇数步的情况，最后一步是随便走的，我们可以对每个集合存一个 set，存集合中能一步走到的点，启发式合并即可
代码1234567891011121314151 ...
【拾题杂谈】CF570D - Tree Requests
题面原题链接大秦 为你打开 题目传送门
题目翻译给定一个以 $1$ 为根的 $n$ 个结点的树，每个点上有一个字母（a-z），每个点的深度定义为该节点到 $1$ 号结点路径上的点数。每次询问 $a, b$ 查询以 $a$ 为根的子树内深度为 $b$ 的结点上的字母重新排列之后是否能构成回文串。
思路首先这道题目一眼就是树上启发式合并，我们大力统计每一个点以及他们的子树里面每个深度每种字母有多少就可以了。代码并没有什么细节敲板子即可。
代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129 ...
【拾题杂谈】CF1709E - XOR tree
题面原题链接大秦 为你打开 题目传送门
题目翻译你有一棵无根树，点数为 $n$，每个点有个点权 $a_u$，定义一条路径 $P(u,v)$ 的权值为经过的所有点的点权的异或和。定义一棵树是合法的，当且仅当树上所有简单路径（只经过每个点一次的路径）的的权值都不为 $0$。
你可以对权值进行修改，可以改成任意正整数，问最少修改多少次才能让这棵树合法。
输出最小修改次数。
$n\leq 2\times 10^5,a_i\leq 2^{30}$
思路我们不难发现，如果一条路径上的元素异或值为 0 我们设 $dep_i$ 表示 $i$ 号点到根所有路径的值。 那么这个路径一定满足条件 $dep_u\ \oplus\ dep_v\ \oplus\ dep_{lca(u,v)} = 0$ 。那么我们就不难想到，处理出这个节点所有儿子的左右子树里的 dep 值。如果 $v$ 的子树之中存在一个值等于 $u$ 的子树中的一个节点的值异或当前这个节点的值，那么一定存在一条路径在这两个子树之中。那么一劳永逸的方式就是把当前这个作为 lca 的节点替换了，统计答案。
代码1234567891011121314 ...
【拾题杂谈】517八段第十三课D
题面题目链接大秦 为你打开 题目传送门
备用题面给定若干未赋值的变量，并给出 $n$ 组操作，每组操作形如：x y p 。当 $p$ 为 $1$ 时，如果第 $x$ 变量和第 $y$ 个变量可以相等，则输出 YES ，并限制他们必须相等；否则输出 NO ，并忽略此次操作。当 $p$ 为 $0$ 时，如果第 $x$ 变量和第 $y$ 个变量可以不相等，则输出 YES ，并限制他们必须不相等；否则输出 NO ，并忽略此次操作。
思路显而易见的相等关系肯定是用并查集存储，而不等关系我们只需要用 vector 存下来有以后大力合并即可。
代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103// #pragma GCC optimize(2)// ...
【拾题杂谈】LuoguP3201 [HNOI2009] 梦幻布丁
题面：[HNOI2009] 梦幻布丁题目描述$n$ 个布丁摆成一行，进行 $m$ 次操作。每次将某个颜色的布丁全部变成另一种颜色的，然后再询问当前一共有多少段颜色。
例如，颜色分别为 $1,2,2,1$ 的四个布丁一共有 $3$ 段颜色.
输入格式第一行是两个整数，分别表示布丁个数 $n$ 和操作次数 $m$。第二行有 $n$ 个整数，第 $i$ 个整数表示第 $i$ 个布丁的颜色 $a_i$。接下来 $m$ 行，每行描述一次操作。每行首先有一个整数 $op$ 表示操作类型：
若 $op = 1$，则后有两个整数 $x, y$，表示将颜色 $x$ 的布丁全部变成颜色 $y$。
若 $op = 2$，则表示一次询问。
输出格式对于每次询问，输出一行一个整数表示答案。
样例 #1样例输入 #1123454 31 2 2 121 2 12
样例输出 #11231
提示样例 1 解释初始时布丁颜色依次为 $1, 2, 2, 1$，三段颜色分别为 $[1, 1], [2, 3], [4, 4]$。一次操作后，布丁的颜色变为 $1, 1, 1, 1$，只有 $[1, 4]$ 一段颜色。
数据规 ...
【算法介绍】启发式合并
算法简介：追加投资启发式合并，我个人觉得和启发没什么关系，主要就是合并的方式，他用一种特殊的合并方式，达到看似暴力的复杂度，实则 $O(n\log n)$ 的复杂度完成问题，是一种相当奇特的算法。
且试身手：特许经营普通启发式合并：百巧千奇首先就是最最基本的启发式合并，上面的简介也说过，所谓启发式合并，重在合并方式。我们如何进行合并，可以使得复杂度降低呢？答案就是：从小到大合并。
为什么这样是正确的？确实，一眼看上去这和普通的合并方式并无区别，我们可以先考虑暴力。那么最最暴力的，随便找两个合并，单次合并的复杂度是 $O(n)$ ，一共要合并 $n-1$ 次，所以复杂度显然是 $O(n^2)$ 。那么如果我们从小到大合并，或者说把小的合并到大的里面会怎么样？
那么我们这边定义集合 $A, B$ ，且集合 $A$ 的大小小于 $B$ 。那么如果把 $A$ 合并入 $B$ ，就会发现，相对于 $A$ 来说，他的大小至少乘二。总共合并了 $n-1$ 次，那么均摊的来讲，这个 $A$ 只会被合并 $\log n$ 次。所有集合的大小加起来一共 $n$ ，总复杂度就是 $O(n\log n)$ 。 ...
【拾题杂谈】LuoguP3709 [AHOI2013] 作业
题面：[AHOI2013] 作业题目描述此时己是凌晨两点，刚刚做了 Codeforces 的小 A 掏出了英语试卷。英语作业其实不算多，一个小时刚好可以做完。然后是一个小时可以做完的数学作业，接下来是分别都是一个小时可以做完的化学，物理，语文……小 A 压力巨大。
这时小 A 碰见了一道非常恶心的数学题，给定了一个长度为 $n$ 的数列和若干个询问，每个询问是关于数列的区间表示数列的第 $l$ 个数到第 $r$ 个数)，首先你要统计该区间内大于等于 $a$，小于等于 $b$ 的数的个数，其次是所有大于等于 $a$，小于等于 $b$ 的，且在该区间中出现过的数值的个数。
小 A 望着那数万的数据规模几乎绝望，只能向大神您求救，请您帮帮他吧。
输入格式第一行两个整数 $n,m$
接下来 $n$ 个不超过 $10^5$ 的正整数表示数列
接下来 $m$ 行，每行四个整数 $l,r,a,b$，具体含义参见题意。
输出格式输出 $m$ 行，分别对应每个询问，输出两个数，分别为在 $l$ 到 $r$ 这段区间中大小在 $[a,b]$ 中的数的个数，以及大于等于 $a$，小于等于 $b$ 的，且在该 ...
【拾题杂谈】LuoguP3709 大爷的字符串题
题面：大爷的字符串题大秦为你打开题目传送门
题目背景在那遥远的西南有一所学校，
/*被和谐部分*/
然后去参加该省省选虐场，
然后某蒟蒻不会做，所以也出了一个字符串题：
题目描述给你一个字符串 $a$，每次询问一段区间的贡献。
贡献定义：
每次从这个区间中拿出一个字符 $x$ ，然后把 $x$ 从这个区间中删除，直到区间为空。你要维护一个集合 $S$。
如果 $S$ 为空，你 rp 减 $1$。
如果 $S$ 中有一个元素不小于 $x$，则你 rp 减 $1$，清空 $S$。
之后将 $x$ 插入 $S$。
由于你是大爷，平时做过的题考试都会考到，所以每次询问你搞完这段区间的字符之后最多还有多少 rp？rp 初始为 $0$。
询问之间不互相影响~
输入格式第一行两个整数 $n$，$m$，表示字符串长度与询问次数。
之后一行 $n$ 个数，第 $i$ 个整数表示给出的字符串的第 $i$ 个字符 $x_i$。
接下来 $m$ 行，每行两个整数 $l, r$，表示一次询问的区间。
输出格式对于每次询问，输出一行一个整数表示答案。
样例 #1样例输入 #1123453 33 3 33 ...
【拾题杂谈】LuoguP1494 [国家集训队] 小 Z 的袜子
题面：[国家集训队] 小 Z 的袜子大秦为你打开题目传送门
题目描述upd on 2020.6.10 ：更新了时限。
作为一个生活散漫的人，小 Z 每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天，小 Z 再也无法忍受这恼人的找袜子过程，于是他决定听天由命……
具体来说，小 Z 把这 $N$ 只袜子从 $1$ 到 $N$ 编号，然后从编号 $L$ 到 $R$ 的袜子中随机选出两只来穿。尽管小 Z 并不在意两只袜子是不是完整的一双，他却很在意袜子的颜色，毕竟穿两只不同色的袜子会很尴尬。
你的任务便是告诉小 Z，他有多大的概率抽到两只颜色相同的袜子。当然，小 Z 希望这个概率尽量高，所以他可能会询问多个 $(L,R)$ 以方便自己选择。
然而数据中有 $L=R$ 的情况，请特判这种情况，输出0/1。
输入格式输入文件第一行包含两个正整数 $N$ 和 $M$。$N$ 为袜子的数量，$M$ 为小 Z 所提的询问的数量。接下来一行包含 $N$ 个正整数 $C_i$，其中 $C_i$ 表示第 $i$ 只袜子的颜色，相同的颜色用相同的数字表示。再接下来 $M$ 行，每行两个正整数 ...
