集训营笔记
本帖汇总了作者参加的集训营中精讲精练的几道题目的解法。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
动态规划篇
例题1
原题：AtCoder_Beginner_Contest 282 G\tt AtCoder\_Beginner\_Contest\,\,282\,\,GAtCoder_Beginner_Contest282G Similar Permutation
洛谷传送门
AtCoder\tt AtCoderAtCoder传送门
题意：对于两个排列 AAA 和 BBB，定义二者的相似度为比大小结果相同的相邻位置对数量，求所有相似度为 kkk 的排列数量，关于大质数 PPP 取模（n≤100n\leq100n≤100）
思路：对于排列而言，基本按照下标或值考虑。
基本想法是：设 dp[i][j][k][l]dp[i][j][k][l]dp[i][j][k][l] 表示考虑前 iii 个数，AAA 序列中第 iii 位为 jjj，BBB 序列中第 iii 位为 kkk，整体相似度为 lll
但是显然这样是不够的，因为排列需要保证每个数都出现恰好 111 次，还需要维护第 iii 个数出现过几次，会导致时间和空间都爆掉。
因而，考虑转换 dp[i][j][k][l]dp[i][j][k][l]dp[i][j][k][l] 的含义，令其表示 已有的 AAA 序列中第 iii 位排名为 jjj，已有的 BBB 序列中第 iii 位排名为 kkk，整体相似度为 lll
注意：这里的排名是 相对的，不是绝对的，因而初始化的时候只能够是 dp[1][1][1][0]=1dp[1][1][1][0]=1dp[1][1][1][0]=1，因为只有一个数的时候排名肯定是第一
接下来考虑转移。
第一种情况：如果当前位置对会产生贡献：
1.1. 如果都小于当前位：
dp[i][j][k][l]=∑a=1j−1∑b=1k−1dp[i−1][a][b][l−1]\displaystyle dp[i][j][k][l]=\sum_{a=1}^{j-1}\sum_{b=1}^{k-1}dp[i-1][a][b][l-1]dp[i][j][k][l]=a=1∑j−1 b=1∑k−1 dp[i−1][a][b][l−1]
1.2. 如果都大于当前位：
dp[i][j][k][l]=∑a=jn∑b=kndp[i−1][a][b][l−1]\displaystyle dp[i][j][k][l]=\sum_{a=j}^{n}\sum_{b=k}^{n}dp[i-1][a][b][l-1]dp[i][j][k][l]=a=j∑n b=k∑n dp[i−1][a][b][l−1]
第二种情况：如果当前位置对不产生贡献：
2.1. 如果 AAA 小 BBB 大：
dp[i][j][k][l]=∑a=1j−1∑b=kndp[i−1][a][b][l]\displaystyle dp[i][j][k][l]=\sum_{a=1}^{j-1}\sum_{b=k}^{n}dp[i-1][a][b][l]dp[i][j][k][l]=a=1∑j−1 b=k∑n dp[i−1][a][b][l]
2.2. 如果 AAA 大 BBB 小：
dp[i][j][k][l]=∑a=jn∑b=1k−1dp[i−1][a][b][l]\displaystyle dp[i][j][k][l]=\sum_{a=j}^{n}\sum_{b=1}^{k-1}dp[i-1][a][b][l]dp[i][j][k][l]=a=j∑n b=1∑k−1 dp[i−1][a][b][l]
由于是相对排名，因而下标应当从 nnn 开始枚举，就像超过第二名你就是第二名，原本第二名变成第三名了一样。
朴素の代码：
时间复杂度：O(n6)O(n^6)O(n6)，空间复杂度：O(n4)O(n^4)O(n4)
因而需要优化时间，由于这里一直是对于一段进行求和，可以使用二维前缀和优化 DP\tt{DP}DP ，降低时间复杂度，可过
注意：这里由于需要不同维度的 lll，因而如果你前缀和只开二维需要两次初始化，浪费一定时间，如果开三维或者四维则可以避免这个问题，但会浪费空间。实测两种方式都可以过
优化后の代码：
时间复杂度：O(n4)O(n^4)O(n4)，空间复杂度：O(n4)O(n^4)O(n4)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
例题2
原题：JOISC 2014\tt JOISC\,\,2014JOISC2014 たのしい家庭菜園
洛谷传送门
AtCoder\tt AtCoderAtCoder传送门
题意：有一个长度为 nnn 的序列 {an}\{a_n\}{an }，只能进行邻项交换操作，让序列变为单峰序列，求最小交换次数（n≤3×105n\leq3\times10^5n≤3×105）
思路：如果是要变成排序后的序列，即单调递增序列的话，那么会很方便
由于一次交换相当于去掉一组逆序对，因此，如果需要让序列变得有序，那么最小交换次数就是逆序对数量。
现在需要变成单峰序列，即 ∃i,s.t.(∀j<i,aj≤aj+1)∧(∀j>i,aj≤aj−1)\exist i,s.t.(\forall j<i,a_j\leq a_{j+1})\land(\forall j>i,a_j\leq a_{j-1})∃i,s.t.(∀j<i,aj ≤aj+1 )∧(∀j>i,aj ≤aj−1 )，
相当于，对于 1≤j≤i1\leq j\leq i1≤j≤i 的 aja_jaj 构成的序列从前往后看单调递增，且 i≤k≤ni\leq k\leq ni≤k≤n 的 aka_kak 构成的序列从后往前看单调递增，
问题转化为，你把任意的 aia_iai 放在前面交换的次数少，还是放在后面交换的次数少
即统计前后逆序对的数量那个更少，
利用树状数组统计逆序对，将所有结果累加即可。
代码：
上面之所以用 a[i]a[i]a[i] 作为get函数的参数，是因为去重的关系
时间复杂度：O(nlogn)O(n\log{n})O(nlogn)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
例题3
原题：P4766 [CERC2014]\tt P4766\,\,[CERC2014]P4766[CERC2014] Outer space invaders
洛谷传送门
题意：有 nnn 个外星人，第 iii 个外星人出现时间段为 a[i]∼b[i]a[i]\sim b[i]a[i]∼b[i]，距离为 d[i]d[i]d[i]，清除距离 ≤R\leq R≤R 的所有外星人费用为 RRR，求将所有外星人都清除的最小费用
思路：朴素区间 DP\tt{DP}DP
先将时间序列 {ai}\{a_i\}{ai } 和 {bi}\{b_i\}{bi } 进行离散化，然后设 dp[L][R]dp[L][R]dp[L][R] 表示干掉时间 a[i]a[i]a[i] 和 b[i]b[i]b[i] 都在区间 [L,R][L,R][L,R] 内所有敌人所需要花费的最少能量
初始化就是时间 [i,i][i,i][i,i] 内每个时间点都是花费 000
考虑转移：枚举断点 kkk，假设所有在时间区间 [L,k−1][L,k-1][L,k−1] 和 [k+1,R][k+1,R][k+1,R] 内的敌人都已经被清除，只需要再清除 ∀i,s.t.L≤a[i]≤k≤b[i]≤R\forall i,s.t.L\leq a[i]\leq k\leq b[i]\leq R∀i,s.t.L≤a[i]≤k≤b[i]≤R，然后加上其中某个敌人的 did_idi ，即 dp[L][R]=mink=L+1R−1dp[L][k−1]+dp[k+1][R]+d[x]\displaystyle
dp[L][R]=\min_{k=L+1}^{R-1}dp[L][k-1]+dp[k+1][R]+d[x]dp[L][R]=k=L+1minR−1 dp[L][k−1]+dp[k+1][R]+d[x]
那么，具体是哪一个敌人的 did_idi ？应当清除最大的 did_idi ，因为如果清除的不是最大的 did_idi ，你还需要花一定的费用来清除它，会造成前面的费用浪费。因而，只需要找到 did_idi 最大的敌人，保证其满足 L≤a[i]≤k≤b[i]≤RL\leq a[i]\leq k\leq b[i]\leq RL≤a[i]≤k≤b[i]≤R，从而进一步优化 kkk 的范围到 [a[i],b[i]][a[i],b[i]][a[i],b[i]]
最终的答案就是清除所有的敌人。设 mmm 为离散化之后所有的时间节点个数，故需要清除所有 a[i]a[i]a[i] 和 b[i]b[i]b[i] 在 [1,m][1,m][1,m] 内的敌人，因此答案为 dp[1][m]dp[1][m]dp[1][m]
代码：
时间复杂度：O(n3)O(n^3)O(n3)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
最优化篇
例题1
原题：CodeForces 632 C\tt CodeForces\,\,632\,\,CCodeForces632C The Smallest String Concatenation
洛谷传送门
CodeForces\tt CodeForcesCodeForces传送门
题意：nnn 个字符串，拼接使得最终字符串字典序最小
思路：假设一个最优解是 s1s2⋯sns_1s_2\cdots s_ns1 s2 ⋯sn ，考虑微调，使得新的解比原来的解更大，不优
使用类似于排序算法的操作，交换相邻位置，或者把元素直接拉到开头或结尾
此处考虑交换相邻两个串的位置。
例如，交换 s1s_1s1 和 s2s_2s2 ，要求 s1s2<s2s1s_1s_2<s_2s_1s1 s2 <s2 s1 ，那么推广到全局，只需要重载 ≤\leq≤ 符号即可，记作 s1⪯s2s_1\preceq s_2s1 ⪯s2
定义 s1⪯s2s_1\preceq s_2s1 ⪯s2 ，那么可知其传递性：若 s1⪯s2,s2⪯s3s_1\preceq s_2,s_2\preceq s_3s1 ⪯s2 ,s2 ⪯s3 ，则 s1⪯s3s_1\preceq s_3s1 ⪯s3
也可从其定义知其反对称性：s1⪯s2s_1\preceq s_2s1 ⪯s2 ，则 s2⪯s1s_2\preceq s_1s2 ⪯s1 不成立
因而总字典序最小的是按照 ⪯\preceq⪯ 的方式排序，然后拼接
代码：
时间复杂度：O(nlogn)O(n\log{n})O(nlogn)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
例题2
原题：AtCoder_Beginner_Contest 225 F\tt AtCoder\_Beginner\_Contest\,\,225\,\,FAtCoder_Beginner_Contest225F String Cards
洛谷传送门
AtCoder\tt AtCoderAtCoder传送门
题意：nnn 张卡片，第 iii 张字符串 sis_isi ，恰选出 KKK 张，任意顺序连接，使得最终字典序最小（n,K≤50n,K\leq50n,K≤50，sis_isi 仅由小写字母构成）
思路：动态规划即可
一、状态表示：设 dp[i][j]dp[i][j]dp[i][j] 表示前 iii 张选出 jjj 个的方案数，
二、转移方程：
如果选：dp[i][j]=min(dp[i][j],dp[i−1][j−1]+s[i])dp[i][j]=\min(dp[i][j],dp[i-1][j-1]+s[i])dp[i][j]=min(dp[i][j],dp[i−1][j−1]+s[i])
如果不选：dp[i][j]=min(dp[i][j],dp[i−1][j])dp[i][j]=\min(dp[i][j],dp[i-1][j])dp[i][j]=min(dp[i][j],dp[i−1][j])
三、初始化：初始化为极大值（例：char(127)）
四、答案：dp[n][K]dp[n][K]dp[n][K]
为了能够保证 DP\tt{DP}DP 的最优化，需要将 sis_isi 提前按照 s1⪯s2s_1\preceq s_2s1 ⪯s2 的方式排序
代码：
时间复杂度：O(n⋅k⋅∣s∣)O(n\cdot k\cdot|s|)O(n⋅k⋅∣s∣)
但是这种做法有问题：若 s1⪯s2s_1\preceq s_2s1 ⪯s2 ，它是从前往后比较，即对于前缀相同有效，对于后缀相同不一定有效，即不一定有 s1+s3<s2+s3s_1+s_3<s_2+s_3s1 +s3 <s2 +s3 ，但是一定有 s3+s1<s3+s2s_3+s_1<s_3+s_2s3 +s1 <s3 +s2
因而需要 从后往前 DP\tt{DP}DP
一、状态表示：设 dp[i][j]dp[i][j]dp[i][j] 表示 后 iii 张选出 jjj 个的方案数，
二、转移方程：
如果选：dp[i][j]=min(dp[i][j],s[−i]+dp[i−1][j−1])dp[i][j]=\min(dp[i][j],s[-i]+dp[i-1][j-1])dp[i][j]=min(dp[i][j],s[−i]+dp[i−1][j−1])
如果不选：dp[i][j]=min(dp[i][j],dp[i−1][j])dp[i][j]=\min(dp[i][j],dp[i-1][j])dp[i][j]=min(dp[i][j],dp[i−1][j])
三、初始化：初始化为极大值（例：char(127)）
四、答案：dp[n][K]dp[n][K]dp[n][K]
代码：
时间复杂度：O(n⋅k⋅∣s∣)O(n\cdot k\cdot|s|)O(n⋅k⋅∣s∣)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
例题3
原题：P11628 [WC2025]\tt P11628\,\,[WC2025]P11628[WC2025] 猫粮
洛谷传送门
题意：给 nnn 只猫分配猫粮，优质猫粮所有没吃饱的猫都会来抢，普通猫粮则不会，需要让所有猫都达到饱腹值 mmm，问能否得到这样的分配方案
思路：显然最坏的情况是每只猫都抢到一袋优质猫粮，因而希望能够让普通猫粮和优质猫粮一对一匹配成 mmm，这是最好的。
当然，也有一种特殊情况，让一只猫全吃普通猫粮吃饱，其他猫能抢到优质猫粮那就给它们配一袋普通猫粮吃饱。然后，最后一只猫吃剩下的两袋优质猫粮吃饱。这也是一种合法方案。
我在做这道题的时候还想到一种特殊情况：一只猫吃一袋优质猫粮和两袋普通猫粮吃饱，另一只猫则吃一袋优质猫粮，这样能否可行？当然，如果有任何一只猫吃了不止两袋猫粮，那么必然有至少一只猫只吃一袋猫粮，这袋猫粮的饱腹值一定是 mmm，但是因为 1≤ai,bi<m1\leq a_i,b_i<m1≤ai ,bi <m，与题设矛盾，所以无需考虑这种情况。
自信满满地把这个代码写完之后一看，得了 656565 分，后来明白了如果剩下一堆饱腹值相等的优质猫粮也是可以的，那么这个时候谁抢到哪一袋优质猫粮就无所谓了，且这个时候剩下的优质猫粮必然是 m2\cfrac{m}{2}2m 。
因而，基本思路就是，用普通猫粮匹配优质猫粮。如果匹配不到，那就普通猫粮匹配普通猫粮。再匹配不到就无解。
对于优质猫粮而言，要么最终剩余的饱腹值只能有一种，要么最终剩下的袋数恰好是两袋，否则也无解。
代码：
时间复杂度：O(n+m)O(n+m)O(n+m)，多组数据忽略不计
这道题如果没哟那个猫粮的限制的话会更难，因而有了限制之后刚到绿题水准，或许还不到，CSP-S或NOIP签到题的感觉，就是比较考验细节
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
例题4
原题：AtCoder_Beginner_Contest 018 C\tt AtCoder\_Beginner\_Contest\,\,018\,\,CAtCoder_Beginner_Contest018C Coins
洛谷传送门
AtCoder\tt AtCoderAtCoder传送门
题意：给定 x+y+zx+y+zx+y+z 个三元组 (ai,bi,ci)(a_i,b_i,c_i)(ai ,bi ,ci )，选择 xxx 个 aia_iai ，yyy 个 bib_ibi ，zzz 个 cic_ici ，使得选择的数的和最大
思路：本题的弱化版本是二元组 (ai,bi)(a_i,b_i)(ai ,bi )，假设全部选择 aia_iai ，然后考虑选择 bib_ibi 带来的额外贡献，按照差值排序。
现在是三元组，也可以这样做，假设全部选择 aia_iai ，那么问题转化成在此条件下选择 yyy 个 bib_ibi 和 zzz 个 cic_ici 能带来的最大的额外贡献。
一道标准的二位偏序贪心题。选择 bib_ibi 的额外贡献是 dbi=bi−aidb_i=b_i-a_idbi =bi −ai ，选择 cic_ici 的额外贡献是 dci=ci−aidc_i=c_i-a_idci =ci −ai ，因而每个三元组可以简化为 (dbi,dci)(db_i,dc_i)(dbi ,dci ) 形式的二元组进行描述
采用邻项交换法，假设对于 (db1,dc1)(db_1,dc_1)(db1 ,dc1 ) 和 (db2,dc2)(db_2,dc_2)(db2 ,dc2 ) 二者而言，选择 db1db_1db1 和 dc2dc_2dc2 会更优，即 db1+dc2>db2+dc1db_1+dc_2>db_2+dc_1db1 +dc2 >db2 +dc1
移项，得 db1−dc1>db2−dc2db_1-dc_1>db_2-dc_2db1 −dc1 >db2 −dc2
因而，按照 dbi−dcidb_i-dc_idbi −dci 进行降序排序，前面一部分选择 dbidb_idbi 的贡献，后面一部分选择 dcidc_idci 的贡献，最后求出贡献的最大值即可。
考虑用堆维护前缀 dbidb_idbi 的贡献前 yyy 大，以及后缀 dcidc_idci 的贡献前 zzz 大，进行预处理，然后从前往后枚举分界线扫一遍，把前半段和后半段的贡献加起来求最大值即可
代码：
时间复杂度：O(nlogn)O(n\log{n})O(nlogn)
这道题应该是很久以前的一道好题了，可以用来练习二位偏序上的最优调整策略，洛谷上评价是紫题，但放在现在肯定不到这个难度。
它唯一的难点在于细节。我就在细节上犯了两个错误，一个是不开 long long 见了祖宗，另一个是 ans 没有赋极小值，因而吃了两发罚时。
不过我一开始把题目看错为“可以从每个人那里拿最多两种硬币”，因而卡了好久，实则一点不难。我不知道如果改成我这个限制之后会简单一点还是难许多。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
组合计数篇
例题1
原题：P1450 [HAOI2008]\tt P1450\,\,[HAOI2008]P1450[HAOI2008] 硬币购物
洛谷传送门
题意：给你 c0,c1,c2,c3c_0,c_1,c_2,c_3c0 ,c1 ,c2 ,c3 四种数，nnn 次询问，每次规定四种数分别有 d0,d1,d2,d3d_0,d_1,d_2,d_3d0 ,d1 ,d2 ,d3 个，问有多少种选数方案使得选出来的数的和恰好为 sss
思路：不难发现这是一个动态规划题。
作者一开始思路是设 dp[i][a][b][c][d]dp[i][a][b][c][d]dp[i][a][b][c][d] 表示用 aaa 个 c0c_0c0 ，bbb 个 c1c_1c1 ，ccc 个 c2c_2c2 ，ddd 个 c3c_3c3 凑出 iii 的方案数，然后一看数据范围吓哭了：ci,di,s≤105c_i,d_i,s\leq10^5ci ,di ,s≤105，时空复杂度都炸了
后来发现这是一道多重背包题，价格为 cic_ici 的物品有 did_idi 个的限制，凑出总共为 sss 的价格，然后让你求方案，大致的转移式为 dp[j]+=dp[j−c[i]]dp[j]+=dp[j-c[i]]dp[j]+=dp[j−c[i]]
由于这个是组合计数专题，老师讲了容斥，因而考虑如何用容斥优化。
上文提到，did_idi 是对于 cic_ici 的限制，不妨去掉限制，则变为完全背包求方案数，然后考虑超过限制的情况，即 cic_ici 用了超过了 did_idi 个，然后就可以容斥求方案数了。
别忘了初始化 dp[0]=1dp[0]=1dp[0]=1！
代码：
时间复杂度：O(smax)O(s_{max})O(smax ) 预处理+O(q)O(q)O(q) 查询
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
例题2
原题：CF559C\tt CF559CCF559C Gerald and Giant Chess
洛谷传送门
CodeForces\tt CodeForcesCodeForces传送门
题意：一个人从网格左上角 (1,1)(1,1)(1,1) 走到右下角 (h,w)(h,w)(h,w)，只能往下或往右走，且不能经过黑色格子，问有多少种走法。
思路：考虑直接设 dp[i][j]dp[i][j]dp[i][j] 表示走到 (i,j)(i,j)(i,j) 的方案数，如果是黑色格子那就是 000，否则就是 dp[i][j]=dp[i−1][j]+dp[i][j−1]dp[i][j]=dp[i-1][j]+dp[i][j-1]dp[i][j]=dp[i−1][j]+dp[i][j−1]，但是由于数据范围过大，h,w≤105h,w\leq10^5h,w≤105，空间炸了。
考虑用总方案数减去经过黑格的方案数，设 dp[i]dp[i]dp[i] 表示走到第 iii 个黑格且不经过其它黑格的方案数，那么可以用容斥做，先用组合数求出所有走到第 iii 个黑格的方案数，再减去走到其它黑格之后再走到当前黑格的方案数即可。
由于要计算其它黑格到当前黑格的方案数，因而这里的“其它黑格”必须要在当前黑格的左上角，按照坐标先进行排序再 DP\tt DPDP。
过程中，由于起始位置是 (1,1)(1,1)(1,1)，因而走到第 iii 个黑格 (xi,yi)(x_i,y_i)(xi ,yi ) 的方案数是 Cxi+yi−2yi−1C_{x_i+y_i-2}^{y_i-1}Cxi +yi −2yi −1
假设一个在第 iii 个黑格左上角的黑格 jjj 坐标是 (xj,yj)(x_j,y_j)(xj ,yj )，那么从 jjj 走到 iii 的方案数为 Cxi+yi−xj−yjyi−yjC_{x_i+y_i-x_j-y_j}^{y_i-y_j}Cxi +yi −xj −yj yi −yj
因而，整个转移方程式为 dp[i]=Cxi+yi−2yi−1−∑1≤j≤i,xj≤xi,yj≤yidp[j]×Cxi+yi−xj−yjyi−yj\displaystyle dp[i]=C_{x_i+y_i-2}^{y_i-1}-\sum_{1\leq j\leq i,x_j\leq x_i,y_j\leq y_i}dp[j]\times C_{x_i+y_i-x_j-y_j}^{y_i-y_j}dp[i]=Cxi +yi −2yi −1 −1≤j≤i,xj ≤xi ,yj ≤yi ∑ dp[j]×Cxi +yi −xj −yj yi −yj
如果把终点 (h,w)(h,w)(h,w) 也理解成一个黑格，那么最终的答案就是 dp[n+1]dp[n+1]dp[n+1]
代码：
时间复杂度：O(n2)O(n^2)O(n2)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
杂题专栏篇
例题1
原题：P2827 [NOIP2016S]\tt P2827\,\,[NOIP2016S]P2827[NOIP2016S] 蚯蚓
洛谷传送门
题意：nnn 个数，每个时刻选择最大的数 xix_ixi 分成 ⌊pxi⌋\lfloor px_i\rfloor⌊pxi ⌋ 和 xi−⌊pxi⌋x_i-\lfloor px_i\rfloorxi −⌊pxi ⌋ 两个数，其余数 +q+q+q，每过 ttt 个时刻输出被选中的数。
过了 mmm 个时刻之后，输出所有数中排名为 ttt 的倍数的数。
思路：一开始被这道题吓到了，但是仔细考虑一下，可以把所有数 +q+q+q 变成分裂的两个数 −q-q−q，统一计算偏移量即可。
这样就变成了每次选择最大数的模拟操作，可以用堆来动态获取最大数
暴力代码：
时间复杂度：>O(mlogn)>O(m\log{n})>O(mlogn)
因而容易超时，实测 858585 分。考虑优化，可以从单调性入手。
首先考虑没有偏移量的情况，即 q=0q=0q=0，设两条蚯蚓长度分别是 x1,x2x_1,x_2x1 ,x2 ，不妨设 x1≥x2x_1\geq x_2x1 ≥x2
因而，在分成两部分之后，有 px1≥px2px_1\geq px_2px1 ≥px2 ，从而得到 ⌊px1⌋≥⌊px2⌋\lfloor px_1\rfloor\geq\lfloor px_2\rfloor⌊px1 ⌋≥⌊px2 ⌋
说明左半部分的单调性同原来的单调性。那么如何证明右半部分的单调性也相同呢？
目标是证明 x1−⌊px1⌋≥x2−⌊px2⌋x_1-\lfloor px_1\rfloor\geq x_2-\lfloor px_2\rfloorx1 −⌊px1 ⌋≥x2 −⌊px2 ⌋
由于题目交代了 0<p<10<p<10<p<1，因而有 x1−x2≥px1−px2x_1-x_2\geq px_1-px_2x1 −x2 ≥px1 −px2 ，其实等号取不到，但这些细节无所谓。
移项：x1−x2+px2≥px1x_1-x_2+px_2\geq px_1x1 −x2 +px2 ≥px1 ，这是为了构造单独的 pxipx_ipxi 的向下取整。
两边同时取整：⌊x1−x2+px2⌋≥⌊px1⌋\lfloor x_1-x_2+px_2\rfloor\geq\lfloor px_1\rfloor⌊x1 −x2 +px2 ⌋≥⌊px1 ⌋
由于 x1,x2∈Zx_1,x_2\in\Zx1 ,x2 ∈Z，因而可以直接取出取整符号：x1−x2+⌊px2⌋≥⌊px1⌋x_1-x_2+\lfloor px_2\rfloor\geq\lfloor px_1\rfloorx1 −x2 +⌊px2 ⌋≥⌊px1 ⌋
最后移项：x1−⌊px1⌋≥x2−⌊px2⌋x_1-\lfloor px_1\rfloor\geq x_2-\lfloor px_2\rfloorx1 −⌊px1 ⌋≥x2 −⌊px2 ⌋
没有偏移量的情况证明完毕，现在考虑有偏移量的情况。
有了偏移量之后，目标是证明 ⌊px1⌋+q≥⌊p(x2+q)⌋\lfloor px_1\rfloor+q\geq\lfloor p(x_2+q)\rfloor⌊px1 ⌋+q≥⌊p(x2 +q)⌋ 以及 x1−⌊px1⌋+q≥x2+q−⌊p(x2+q)⌋x_1-\lfloor px_1\rfloor+q\geq x_2+q-\lfloor p(x_2+q)\rfloorx1 −⌊px1 ⌋+q≥x2 +q−⌊p(x2 +q)⌋
先来看第一个式子，由于 qqq 是整数，放入取整符号对结果没有影响，因而有：
⌊px1⌋+q=⌊px1+q⌋≥⌊px2+q⌋≥⌊px2+pq⌋=⌊p(x2+q)⌋\lfloor px_1\rfloor+q=\lfloor px_1+q\rfloor\geq\lfloor px_2+q\rfloor\geq\lfloor px_2+pq\rfloor=\lfloor p(x_2+q)\rfloor⌊px1 ⌋+q=⌊px1 +q⌋≥⌊px2 +q⌋≥⌊px2 +pq⌋=⌊p(x2 +q)⌋
再来看第二个，即证：x1−⌊px1⌋≥x2−⌊p(x2+q)⌋x_1-\lfloor px_1\rfloor\geq x_2-\lfloor p(x_2+q)\rfloorx1 −⌊px1 ⌋≥x2 −⌊p(x2 +q)⌋
根据上面没有偏移量的情况，知 x1−⌊px1⌋≥x2−⌊px2⌋x_1-\lfloor px_1\rfloor\geq x_2-\lfloor px_2\rfloorx1 −⌊px1 ⌋≥x2 −⌊px2 ⌋
现在变成 ⌊p(x2+q)⌋\lfloor p(x_2+q)\rfloor⌊p(x2 +q)⌋，减得东西不可能变少，因而答案不可能变大，即：
x1−⌊px1⌋≥x2−⌊px2⌋≥x2−⌊p(x2+q)⌋x_1-\lfloor px_1\rfloor\geq x_2-\lfloor px_2\rfloor\geq x_2-\lfloor p(x_2+q)\rfloorx1 −⌊px1 ⌋≥x2 −⌊px2 ⌋≥x2 −⌊p(x2 +q)⌋
因而得证。
综上，我们证明了蚯蚓被切断之后的单调性，因而可以把优先队列替换成普通的队列，切断后左右两段依然满足单调性。
维护三个队列，分别存储原来的蚯蚓、切断后左半部分蚯蚓、右半部分蚯蚓即可。
代码：
时间复杂度：O(m)O(m)O(m)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
例题2
原题：P10998\tt P10998P10998 Tuple+
洛谷传送门
题意：给定 mmm 个三元组 (u,v,w)(u,v,w)(u,v,w) 保证 u<v<wu<v<wu<v<w，求有多少个四元组 (u,v,w,t)(u,v,w,t)(u,v,w,t) 满足 u<v<w<tu<v<w<tu<v<w<t
思路：设 S(u,v)S(u,v)S(u,v) 表示能够和 (u,v)(u,v)(u,v) 形成三元组的 www 构成的集合，
则对于每个三元组 (u,v,w)(u,v,w)(u,v,w) 统计 S(u,v)⋂S(v,w)⋂S(u,w)S(u,v)\bigcap S(v,w)\bigcap S(u,w)S(u,v)⋂S(v,w)⋂S(u,w) 即可
代码:
时间复杂度：O(m43)O(m^\frac{4}{3})O(m34 )
