值域有交平衡树合并及复杂度证明
以下内容理论上对多种平衡树都成立，但是此处假设这个只是对 FHQ Treap 成立。
合并
对于两棵树 l,rl,rl,r ，设 lll 树根的优先级大于 rrr ，那么先判断他们值域是否有交，如果没有交那么直接用 FHQ 的合并就行。如果有交就按照 lll 的权值将 rrr 分裂后将 lll 的两个儿子分别和分裂出来的子树合并。
例如如下代码：
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253void split(int p,int x,int &l,int &r){ if(!p)return (void)(l=r=0); down(p); if(val[p]<=x){ l=p; split(son[p][1],x,son[p][1],r); } else{ r=p; split(son[p][0] ...
CF1175G Yet Another Partiton Problem
人生中第三次写出特别强的黑题。
题目链接： CF1175G Yet Another Partiton Problem 。
题目描述：
给定一个数组 a1,a2,…,ana_1, a_2, \dots, a_na1,a2,…,an，你需要将其分成 kkk 个子段（每个元素恰好属于一个子段）。
一个子段 al,al+1,…,ara_l, a_{l+1}, \dots, a_ral,al+1,…,ar 的权值定义为 (r−l+1)⋅maxl≤i≤r(ai)(r - l + 1) \cdot \max\limits_{l \le i \le r}(a_i)(r−l+1)⋅l≤i≤rmax(ai)。一个划分的权值是所有子段权值之和。
请你找到权值最小的划分方案。
n≤2×104,k≤100n\le 2\times 10^4,k\le 100n≤2×104,k≤100 。
时限 5s5s5s ，空间限制 500MB500MB500MB 。
根据范围可以猜测正解时间为 O(nklogn)O(nk\lo ...
[APIO2013] 出题人
难得我会写的构造。
题目链接： [APIO2013] 出题人 。
题目描述：
当今世界上各类程序设计竞赛层出不穷。而设计一场好比赛绝非易事，比如给题目设计测试数据就是一项挑战。一组好的测试数据需要对不同的程序有区分度：满足所有要求的程序自然应该得到满分，而那些貌似正确的程序则会在某些特殊数据上出错。
在本题中，你在比赛中的角色反转啦！作为一名久经百战的程序员，你将帮助 Happy Programmer Contest 的命题委员会设计这次比赛的测试数据。本次比赛命题委员会选择了两个图论问题，分为 888 个子任务。委员会写了一些貌似可以解决这些子任务的代码。在给任务设计数据的时候，命题委员会期望其中的一些源程序能够得到满分，而另外的一些则只能得到 000 分或者少许的部分分。现在你将会获得这些源程序（C, C++, Pascal 版本）。对于每个子任务，你需要去产生一组数据 XXX 使得它能将该任务给定的 222 种源程序 AAA 和 BBB 区分开来。更具体地说，生成的数据必须满足如下两个条件:
输入 XXX 对于源程序 AAA 一定不会出现超出时间 ...
[NOI2024] 登山
这是第一个我自己写出来的树形 DP 黑题。
题目链接： [NOI2024] 登山 。
题目描述：
“为什么要攀登？因为山就在那里。”
慕士塔格山上有 nnn 处点位，点从 111 到 nnn 编号，111 号点位为山顶。这 nnn 个点位构成一棵有根树的结构，其中 111 号点位为根，对于 2≤i≤n2\leq i\leq n2≤i≤n，iii 号点位的父亲结点为 pip_ipi 号点位。
记 did_idi 为 iii 号点位到山顶所需经过的边数。形式化地说，d1=0d_1=0d1=0，对于 2≤i≤n2\leq i\leq n2≤i≤n，di=dpi+1d_i=d_{p_i}+1di=dpi+1。
定义一条登山路径为从 2∼n2\sim n2∼n 号点位中的某一个开始，经过若干次移动后到达山顶的方案。
定义一次从 i(2≤i≤n)i(2\leq i\leq n)i(2≤i≤n) 号点位出发的移动为以下两种方式之一：
冲刺：在给定的冲刺范围 [li,ri][l_i,r_i][li,ri] 内，选择一个正整数 kkk 满足 li≤k≤ri ...
NOI 记
加油 NOI 。
P5755 [NOI2000] 单词查找树
【模板】字典树。
题目链接： [NOI2000] 单词查找树 。
题目描述：
在进行文法分析的时候，通常需要检测一个单词是否在我们的单词列表里。为了提高查找和定位的速度，通常都要画出与单词列表所对应的单词查找树，其特点如下：
根节点不包含字母，除根节点外每一个节点都仅包含一个大写英文字母；
从根节点到某一节点，路径上经过的字母依次连起来所构成的字母序列，称为该节点对应的单词。单词列表中的每个词，都是该单词查找树某个节点所对应的单词；
在满足上述条件下，该单词查找树的节点数最少。
对一个确定的单词列表，请统计对应的单词查找树的节点数（包括根节点）。
这个题有意思的点是，它直接把字典树是啥告诉你了，所以这也是一个简单模拟题。
代码：
12345678910111213141516171819202122232425#include <bits/stdc++.h>using namespace std;const int N=100010;string s;int nxt[N][26];int ...
省选联考记
加油省选。
P7518 [省选联考 2021 A/B 卷] 宝石
这个算是一个比较基础的倍增题目了。
题目链接： [省选联考 2021 A/B 卷] 宝石 。
题目内容:
给一颗树，树上每个点有点权。
每次求序列 P1,P2,...PcP_1,P_2,...P_cP1,P2,...Pc （ ccc 为每次询问给的， PPP 为预先定好的序列）是否是 sss 到 ttt 路径上点权构成的序列的子序列。
n,q≤2×105n,q \le 2\times 10^5n,q≤2×105 。
这个信息并不好维护。但是考虑到 PPP 为定序列，我们可以预处理树上每个点 iii 往上走，跨越 PPP 序列上 2j2^j2j 个点后到达的点。
对于 PPP 序列的正序和逆序都需要倍增存储。
这个东西是可以通过可持久化线段树维护的。
设正序倍增数组为 upi,jup_{i,j}upi,j ，逆序为 dni,jdn_{i,j}dni,j 。
那么首先我们求出 s,ts,ts,t 的 lcalcalca ，设为 lll 。
然后倍增跳跃，每次比较跳到的点和 lll 的深度，从而比 ...
UGreen Cloud-space: A better choice for cloud-space
Have you ever been anxious for a big and free cloud-space?
Have you erer used Baidu Cloud-space or Quark Cloud-space and been angry when your VIP was due?
Let’s use UGreen Cloud-Space!
The common aspects of UGreen Cloud-space
UGreen Cloud-space is a website which can memorize your files which you want to upload.
Like other cloud-spaces, UGreen Cloud-space enable you to upload or download your files whenever you click choice “Upload” or “Downl ...
[NOIP2022] 建造军营
题目： [NOIP2022] 建造军营 。
这是我第一个自己写出来的组合数学和树形 DP 的题目。
题目内容：
给定 nnn 个点 mmm 条边的无向联通简单图，可以在任意多个点（至少一个）建立军营，在任意多条边建立士兵。
求有多少种建造方案数使得任意切断一条没有士兵的边后，所有军营依然联通。
n≤5×105,m≤106n \le 5\times 10^5,m\le 10^6n≤5×105,m≤106 。
时间限制 1.00s1.00s1.00s ，内存限制 512.00MB512.00MB512.00MB ，期望复杂度 O(n+m)O(n+m)O(n+m) 。
首先，看到这个题目，这其中 所有军营依然联通 的限制让我们想到边双缩点后在树上求解，这是因为在边双中任意断边后边双内任意两点仍然联通。
问题就转变为了在一个树上求解。
设一个边双 iii 内有 aia_iai 个点和 bib_ibi 条边。
如果设 fif_ifi 表示以 iii 为根的子树内的答案， ∑bi\sum b_i∑bi 为以 iii 为根的子树内的边数，那么这里我们需要 ...
转置原理
初等矩阵
众所周知，矩阵的初等变换有以下三种：
交换第 iii 行（列）和第 jjj 行（列）。
将第 iii 行（列）乘上 kkk 。
将第 iii 行（列）的 kkk 倍对应加到第 jjj 行（列）上。
同时，我们还知道单位矩阵 III ：
[10⋯001⋯0⋮⋮⋮⋮00⋯1]\begin{bmatrix}
1 & 0 & \cdots & 0 \\
0 & 1 & \cdots & 0 \\
\vdots & \vdots & \vdots & \vdots \\
0 & 0 & \cdots & 1
\end{bmatrix}⎣⎢⎢⎢⎢⎡10⋮001⋮0⋯⋯⋮⋯00⋮1⎦⎥⎥⎥⎥⎤
对于任意矩阵 AAA ，有 A×I=I×A=AA\times I=I\times A=AA×I=I×A=A 。
若将初等变换作用在 III 上，就可以得到初等矩阵 EEE ：
对于初等行变换，则 E×AE \times AE×A 为对 AAA 进行初等行变换。
对于初等列变 ...
数论
我为什么会写这个？
整除分块
如果你想在 O(n)O(\sqrt{n})O(n) 时间内求解如下式子：
∑i=1nf(i)g(⌊ni)⌋\sum_{i=1}^n f(i)g(\lfloor\frac{n}{i})\rfloor
i=1∑nf(i)g(⌊in)⌋
满足 O(1)O(1)O(1) 求取 fff 函数的前缀和， O(1)O(1)O(1) 求取 ggg 函数单点值。
这时候就需要用到整除分块了。
看引理：
引理 1 ：
⌊ni⌋\lfloor\frac{n}{i}\rfloor⌊in⌋ 的不同取值个数为 O(n)O(\sqrt{n})O(n) 个。
引理 2 ：
对于整数 kkk ，对于所有的 iii 满足 ⌊ni⌋=k\lfloor\frac{n}{i}\rfloor=k⌊in⌋=k ， iii 的取值连续。
那么我们可以枚举这 O(n)O(\sqrt{n})O(n) 个取值，从而在 O(n)O(\sqrt{n})O(n) 内求解。
但是我们还有一个问题：假设当前枚举的取值为 ⌊nl⌋\lfloor\frac{n}{l}\rfloor⌊ln ...
