P3810 【模板】三维偏序（陌上花开）
闲扯咕了不知道多久的 $CDQ$ 分治，今天终于初步学了一下。。
题面P3810 【模板】三维偏序（陌上花开）
Solution$CDQ$ 能解决的最基础的问题是二维偏序问题，例如树状数组的单点加和区间求和。
当问题拓展到三维时，我们需要先对其中一维排一下序，这样问题就剩下两维了。
但是我们能处理的
...
SP2713 GSS4 - Can you answer these queries IV
发表于
闲扯这题数据也太扯了吧，居然不保证 $l<r$ 。。。
题面SP2713 GSS4 - Can you answer these queries IV
Solution我们可以发现，在 $10^{18}$ 的范围内，最大的 $10^{18}$ 最多开 $6$ 次根号就会变成 $1$ ，而 $1
...
P2634 [国家集训队]聪聪可可
发表于
闲扯点分治果然很多都是模板啊
题面P2634 [国家集训队]聪聪可可
Solution我们可以知道，一共有 $n^2$ 中选法，所以我们只需要统计距离为 $3$ 的倍数的点对即可。
因为两点间可以互换位置，求出答案之后要乘上二。又因为自己到自己的距离为 $0$ ，所以最后还要加上 $n$ 。
因为要
...
P4178 Tree
发表于
闲扯淀粉质好水题。
题面P4178 Tree
Solution先套上点分治模板。
因为我们要求距离小于等于 $k$ 的点对个数，且 $k\leq 20000$ ，我们可以用树状数组维护当前已经遍历了的子树中离分治中心距离为 $i$ 的点的个数。
每次查询，我们可以找到其他子树中的点和某节点组成的合法
...
P3806 【模板】点分治1
发表于
闲扯我重心找错了，分治的时候没递归处理分治中心，直接处理子节点，结果还可以过题？？？？？
我真的是佛了。。
题面P3806 【模板】点分治1
Solution点分治的模板题。但是话说点分治不都是套模板吗。。
套路性的，我们先找到树的重心，以重心作为分治中心处理。
依次遍历中心的每一个子树，找到当前子
...
P3521 [POI2011]ROT-Tree Rotations
发表于
闲扯$LOJ$ 果然是毒瘤，这道题时限居然只开 $160ms$ ，我也是醉了。还是洛谷友善
题面P3521 [POI2011]ROT-Tree Rotations
Solution我们可以发现对一个点的两颗子树进行交换，只会影响到这两颗子树之间的贡献，对其他的没有影响。（除去这两颗子树外，在你前面的
...
P3224 [HNOI2012]永无乡
发表于
闲扯找了好久的 $FHQ-Treap$ 的启发式合并，终于找到了，但是题解里面为毛全是 $splay$ 和线段树合并啊。。。
少有的几篇 $FHQ$ 的题解，结果基本都是指针的，只有一片能看。。。
题面P3224 [HNOI2012]永无乡
Solution平衡树因为要查询第 $K$ 大，很容易想到
...
P3201 [HNOI2009]梦幻布丁
发表于
闲扯冲着学启发式合并来做的题，结果发现完全不懂其中的一些细节啊。。。
最后还是看了题解里面大佬的解释才想通。
题面P3201 [HNOI2009]梦幻布丁
Solution考虑对每一种颜色开一个平衡树，那么我们每次操作相当于是合并两颗平衡树。
直接暴力合并复杂度显然是不对的，考虑启发式合并。
每次将
...
UVA11584 划分成回文串 Partitioning by Palindromes
发表于
闲扯这道题不是一个字符串 $hash$ 的题吗，为啥题解全部都是区间 $DP$ 求回文串。。。
题面UVA11584 划分成回文串 Partitioning by Palindromes
Solution我们先不考虑回文串的问题，考虑怎么求解这个问题。
显然，我们设 $dp_i$ 表示前 $i$ 位
...
P4254 [JSOI2008]Blue Mary开公司
发表于
闲扯出了一个玄学问题，结果 $JKLover$ 帮我找了半天的错。。
题面P4254 [JSOI2008]Blue Mary开公司
Solution考虑李超线段树。
对于线段树的每一个区间，我们记录该区间的优势线段。
$ps:$ 优势线段是指在该区间内满足所有线段都不超过它的线段
对于插入线段，我们
...