省选集训
AC_Lover
·
·
个人记录
原题：[JOI 2025 Final] 缆车 / Mi Teleférico
赛时做法： 没有挖掘出性质，打了暴力部分分
正解：
性质： 考虑什么时候从1号点出发可以到达1到n的其他点，发现这个图满足条件的充分必要条件是除1以外的点的入度都不为0。并且如果保留[L,R]可行，那么保留[L^\prime,R^\prime]\supseteq[L,R]也可行
我们可以先考虑如何判断保留[L,R]是否可行，我们定义nxt_i表示最小的j使得[i,j]可行，由性质，可以将边权排序，用双指针扫描并维护每个点的入度以及此时入度为0的点的个数，即可求出nxt_i
求出后，如果R\ge nxt_L那么[L,R]区间包含了可行的[L,nxt_L]，那么此时[L,R]可行
接下来考虑|L-L^\prime|+|R-R^\prime|\le X_i的限制，考虑左端点L^\prime和右端点R^\prime，
对于其中L^\prime=L或R^\prime=R的情况是简单的，贪心计算，而对于剩下的情况：
可以发现此时一定有L^\prime<L，
因为如果L^\prime\ge L：
-----L---L`---R-----R`
那么将多出L的那部分对称到左边此时绝对值没有变化但是选择的区间变大了，一定不劣，
所以L^\prime<L，并且可以同理贪心得到L^\prime\le R
由于要满足[L^\prime,R^\prime]可行，所以R^\prime \ge nxt_{L^\prime}，现在分类讨论R^\prime的取值，
当R^\prime \le R时，代价为L-L^\prime+R-R^\prime，即L+R-(L^\prime+R^\prime)，为了让代价尽可能的小，要使得L^\prime+R^\prime尽可能的大，于是此时要让L^\prime和R^\prime尽可能大，于是我们用贪心思想，找到使得nxt_{L^\prime}\le R的最大的L^\prime，然后R^\prime取R即可取到最大
当R^\prime>R时，代价为L-L^\prime+R^\prime-R，即L-R+R^\prime-L^\prime，此时要R^\prime-L^\prime尽可能小，于是我们贪心的选择R^\prime=nxt_{L^\prime}，这样可以用ST表维护区间nxt_{L^\prime}-L^\prime的最小值，记使得nxt_{L^\prime}\le R的最后一个点为pos，那么[pos+1,R]中nxt_{L^\prime}-L^\prime的最小值就对应了R^\prime-L^\prime的最小值
对于上述的五种情况分别计算即可。
此题中P的范围较大，难以处理，但是我们发现L、L^\prime、R、R^\prime都会分别取到一个C_i上，同样可以用贪心证明，于是我们可以对C_i离散化，用二分找到L、R的位置然后计算即可。
原题：
P3515 [POI 2011] Lightning Conductor
对于每个i求一个最小的非负整数p，使得\forall j\in[1,n]，都有：a_j\le a_i+p-\sqrt{|i-j|}
n\le 5\times 10^5
正解：
移项得到p+a_i\ge a_j+\sqrt{|i-j|}，即只需要对每个a_i求出\max_{1\le j\le i}\{a_j+\sqrt{|i-j|}\}
绝对值可以通过前后分别扫一遍去掉，于是化简掉得\max_{1\le j\le i}\{a_j+\sqrt{i-j}\}
定义f_i=\max_{1\le j\le i}\{a_j+\sqrt{i-j}\}，此时我们定义w(j,i)=\sqrt{i-j}
考虑w(j,i)是否满足四边形不等式，
对于a<b，
w(a,b+1)+w(a+1,b)=\sqrt{a-b-1}+\sqrt{a-b+1} \\
w(a,b)+w(a+1,b+1)=\sqrt{a-b}+\sqrt{a-b}=2\sqrt{a-b} \\
\therefore w(a,b+1)+w(a+1,b)-[w(a,b)+w(a+1,b+1)]= \\
\sqrt{a-b-1}+\sqrt{a-b+1}-2\sqrt{a-b} \\
令T=a-b，原式= \\
\sqrt{T-1}+\sqrt{T+1}-2\sqrt{T} \\
=(\sqrt{T+1}-\sqrt{T})-(\sqrt{T}-\sqrt{T-1}) \\
由于函数f(x)=\sqrt{x+1}-\sqrt{x}单调递减， \\
\therefore \sqrt{T+1}-\sqrt{T}<\sqrt{T}-\sqrt{T-1}\\
\therefore 原式<0 \\
所以有：
w(a,b+1)+w(a+1,b)\le w(a,b)+w(a+1,b+1)
由定理推广可以得到定义域内的任意整数a\le b\le c\le d
w(a,d)+w(b,c)\le w(a,c)+w(b,d)
由于此题求的是\max，所以将四边形不等式决策单调性证明的符号反过来就可以得到此题中的f满足决策单调性
于是用队列/分治即可优化DP，O(n\log n)解决此题
原题：
珠宝 /「NAIPC2016」Jewel Thief
$n\le 10^6,K\le 5\times 10^4,c_i\le 300
正解：
定义f_{c,i}表示考虑c_i\le c的物品，大小为i的背包所能获得的最大价值
用w(c,k)表示j个重量为c的物品所能获得的最大价值
考虑体积固定为i，有状态转移方程：
{\large f_{c,i}=\max_{0\le j \le \frac{i}{c}}\{f_{c-1,i-jc}+w(c,j)\}}
可以看成：
{\large f_{i}=\max_{0\le j \le \frac{i}{c}}\{g_{i-jc}+w(c,j)\}}
考虑按照i\bmod c来分组，枚举r表示i\bmod c=r的组，那么i=r+xc,i-jc=r+xc-jc=r+(x-j)c，于是
{\large f_{r+xc}=\max_{0\le j \le x}\{g_{r+(x-j)c}+w(c,j)\}}
预处理出pos_p=r+pc，式子即可转化，看成
{\large f_{pos_{x}}=\max_{0\le j \le x}\{g_{pos_{x-j}}+w^\prime(j)\}}
即
{\large f_{pos_{x}}=\max_{0\le j \le x}\{g_{pos_{j}}+w^\prime(x-j)\}} \\
{\large f_{pos_{x}}=\max_{0\le j \le x}\{g_{pos_{j}}+w^{\prime\prime}(x,j)\}}
发现w^{\prime\prime}满足四边形不等式，于是有决策单调性，优化，做完了。
时间复杂度：O(\sum_{c=1}^{m}m\frac{m}{c}\log \frac{m}{c})=O(m(\sum_{c=1}^{C}\log \frac{m}{c}))=O(Cm\log m)
原题： P10736 [SEERC 2020] Archeologists
正解：
考虑将原问题转化为区间覆盖问题
我们将挖格子看作用若干个区间去覆盖这些格子
下面定义的区间是没有与其他区间"相接"的，即不会同时有 [l,k] 和 [k+1,r] 存在，这两个区间会合并成 [l,r]
我们将第i个格子下挖的深度看成这个格子被多少个区间覆盖，于是我们考虑要满足什么条件下挖的深度才能满足要求。
我们发现，每个点只会作为区间的左端点/右端点至多1次
反证法：
假设一个点被作为左端点/右端点大于1次，那么覆盖的次数的差就会大于1，根据区间的定义，此时区间无法调平覆盖次数的差，于是就不满足条件，命题得证
所以我们完成了转化，相当于要选出若干个区间，使得每个格子只会作为区间的左端点/右端点至多一次。
假设一个覆盖区间为 [l,r]，那么其贡献就是 \sum_{i=l}^{r}p_i
相当于要使得选出的区间和最大化。
记sum为p的前缀和数组，那么一段区间的和就可以用 sum_r-sum_l 的形式表示，考虑反悔贪心，每次将选为区间左端点的 sum 值放入小根堆中，对于sum_i，从小根堆中找出最小的sum，判断与之匹配是否更优，反悔贪心即可。
原题： ()
给你一个长度为 2n的括号串，保证其中有 n个左括号，n个右括号。
现在你想在这 2n个位置选一个非空集合 S。集合 S是好的，当且仅当，你可以任意交换 S中这些位置的括号，使得括号是一个合法的括号序列。
现在问有多少个位置集合是好的，由于答案很大，输出对998244353取模的结果。
正解：
计数 \mathrm{dp}
考虑到判断一个括号序列是否合法的依据是前缀和,于是考虑把前缀和放进状态里。由于拿出来的括号的排列方式一定是左括号一边右括号一边，于是再记录一个“阶段”的状态，表示当前选定的位置是放左括号还是右括号。
令 f_{i,j,0/1} 表示考虑前 i 个括号，前缀和为 j，当前选定的位置是放左括号还是右括号。
考虑 i 这个位置，可以选择不选/选择并被改为左括号/选择并被改成右括号。
不选就直接加上前缀和：
f_{i,j,d}\leftarrow^+ f_{i-1,j-w,d}
选为左括号，贡献为 1：
f_{i,j,0}\leftarrow^+ f_{i-1,j-1,0}
选为右括号，贡献为 -1：
f_{i,j,1}\leftarrow^+ f_{i-1,j+1,0} \\
f_{i,j,1}\leftarrow^+ f_{i-1,j+1,1} \\
考虑这个 \mathrm{dp} 的正确性，由于这个位置钦定的括号在合法状态下一定会再选一个与之匹对，所以我们钦定一个位置的括号状态是正确的。
原题： CF1707E
正解：
挖掘f([l,r])的性质，我们发现
如果[L_1,R_1]\cap [L_2,R_2]\ne \emptyset，那么有f([L_1,R_1]\cup [L_2,R_2])=f([L_1,R_1])\cup f([L_2,R_2])
这说明我们可以用\mathrm {ST}表维护区间的f([l,r])。而对于答案的求解，我们考虑倍增，因为如果能达到f([1,n])那么f^k([1,n])=[1,n]，能用倍增
具体的，用\mathrm {ST}_k表示f^{2^k}的\mathrm {ST}表，这样可以O(n\log^2n)的预处理后O(1)查询f^{2^k}([l,r])
这样可以用类似于\mathrm {lca}的求解方法倍增得到答案
时间复杂度：O(n\log^2 n+m\log n)
原题：简单题
赛时做法： 直接暴搜结果假了O(1)次之后获得了0 \mathrm{pts}
正解：
虽然n\le 14，但是这题的方案数之多已经使得暴搜复杂度过高。
考虑使用状压\mathrm {DP}，具体的，定义f_{s,u}表示要用u号点去给点集s中的点传递消息所需要的最小时间
枚举u的每条出边u\to v，如果已经求出了u向点集S传递信息的最小时间f_{S,u}，以及从v向点集T传递时间的最小时间f_{T,v}，我们就可以计算出点u向点集S\cap T传递信息的最小时间f_{S\cap T,u}，有
f_{S\cap T,u}\leftarrow w(u,v)+\max(f_{S,u},f_{T,v})
注意此时要求S\cup T=\emptyset，因为如果S\cup T\ne \emptyset那么可能出现S中的点给T中的点传递消息，与转移不符。
发现S,T\le S\cap T，所以转移可以直接枚举s，找到S\cap T=s\wedge S\cup T=\emptyset，然后枚举u，转移即可。发现满足条件的S,T一定有S\subseteq s,T=s-S，所以合法的S,T状态数规模只有s的子集数，因此复杂度可以做到O(n3^n)
原题：次方数
赛时做法： \mathrm{O}分
正解：
运用\mathrm{Tricks}中【判断序列一个区间内某些数出现次数是否是k的倍数】和【"伪素数"】
先考虑较为优的暴力
将【判断序列一个区间内某些数出现次数是否是k的倍数】的哈希做法扩展一下，将每个数分解质因数后每个质因子编个号，扫描每个区间，维护区间中每个质因子出现次数，标号为i的出现了c_i次。
搞两个区间和s_{0,l,r},s_{1,l,r}，分别记录区间中v_i=c_i\bmod k的哈希值，以及区间v_i=(k-c_i\bmod k)的哈希值（特别的，对于c_i\bmod k=0有v_i=0），这样我们就可以做到O(1)判断[l_1,r_1]和[l_2,r_2]中所有质因子的出现次数和是不是都是k的倍数，具体的，如果s_{0,l_1,r_1}=s_{1,l_2,r_2}那么根据s_0和s_1的定义可以发现满足条件
所以可以枚举l_1,r_1,l_2,r_2中的l_2，开一个桶，桶中记录所有l\le r<l_2的s_{0,l,r}，枚举r_2，取出桶中s_{1,l_2,r_2}的个数，然后桶更新以l_2为右端点的即可。
暴力分解质因数复杂度：O(n^2\sqrt{V})
考虑使用伪素数\mathrm {Trick}优化分解，但此时要注意如果对于一个\mathcal {P}_i其可以表示成x^{\alpha},\alpha>1并且\alpha|k，应将其继续分解，否则可能一些数的乘积在分解后的\mathcal {P}_i^\prime下已经满足条件但是在分解前的\mathcal {P}_i下还不够次数。
这样可以优化分解复杂度到单次O(\log V)，总复杂度O(n^2\log V)
原题：签到题
赛时做法： 大脑刚开始宕机，把n-3条不相交的对角线想成了只能从同一个点出发，准备对拍时才突然发现不对，按正确题面做发现不会正解，没打暴力，直接交歪解，卡成了\mathrm {O pts}
正解：
直接上结论：有解当且仅当每种颜色都出现至少1次并且相邻两个珠子颜色不同。
然后我们考虑每一次连接的对角线
可以发现，如果一个点x其对应颜色的出现次数大于1，并且其左边的点和其右边的点的颜色不同，记其左边的点编号为L_x,右边为R_x，那么可以连接对角线L_xR_x。
然后剩下就跟x没有关系了，此时可以相当于删除了x，正确维护L,R后，原来的n边形就变成了n-1边形，继续求解，直到n=3时没有对角线可以划分，结束。
证明正确性：
三个点L_x,x,R_x，如果x的颜色出现个数大于1，那么x就是所求的，否则x的颜色出现个数一定为1，这时x,R_x,R_{R_x}中，有x的颜色和R_x的颜色不同，R_x的颜色与R_{R_x}的颜色不同，由于x的颜色出现次数为1，所以也有x和R_{R_x}的颜色不同，所以三个点的颜色都不同，同理可以得到L_{L_x},L_{x},x三个点的颜色都不同，这是发现不可能L_x和R_x的出现次数都为1，因为如果发生这种情况说明此时到了n=3，不会再进行操作，因此L_x,R_x中一定有一个颜色出现次数大于1，因此一定有一个满足条件。
如果直接按照多边形n\to n-1 \to \dots 3处理，复杂度为O(n^2)，无法通过，考虑优化。
可以开一个队列，表示当前边数下所有可能作为删除的点的预选队列，开始时每个点都在队列中。每次取出队头，判断，如果满足可以删除那么删除，同时多边形边数减少1，这时L_x,R_x需要重新加入队列中作为备选项。
这样，就可以O(n)解决。
原题：简单题
赛时做法： 打表找规律技术过于低下，未能发现规律，暴搜打表\mathrm {40pts}
正解：
做法来自\mathrm {ysn}
考虑<u>打表</u>，打最优集合的表：
1
2 3
2 3 5
2 3 5 7
4 5 6 7 9
4 5 6 7 9 11
4 5 6 7 9 11 13
4 6 7 9 10 11 13 15
4 6 7 9 10 11 13 15 17
4 6 7 9 10 11 13 15 17 19
4 6 9 10 11 13 14 15 17 19 21
4 6 9 10 11 13 14 15 17 19 21 23
4 6 9 10 11 13 14 15 17 19 21 23 25
8 10 11 12 13 14 15 17 18 19 21 23 25 27
8 10 11 12 13 14 15 17 18 19 21 23 25 27 29
8 10 11 12 13 14 15 17 18 19 21 23 25 27 29 31
8 10 12 13 14 15 17 18 19 21 22 23 25 27 29 31 33
8 10 12 13 14 15 17 18 19 21 22 23 25 27 29 31 33 35
8 10 12 13 14 15 17 18 19 21 22 23 25 27 29 31 33 35 37
8 10 12 14 15 17 18 19 21 22 23 25 26 27 29 31 33 35 37 39
8 10 12 14 15 17 18 19 21 22 23 25 26 27 29 31 33 35 37 39 41
8 10 12 14 15 17 18 19 21 22 23 25 26 27 29 31 33 35 37 39 41 43
8 12 14 17 18 19 20 21 22 23 25 26 27 29 30 31 33 35 37 39 41 43 45
8 12 14 17 18 19 20 21 22 23 25 26 27 29 30 31 33 35 37 39 41 43 45 47
发现
对于长度为n的集合，每一次是向末尾添加一个奇数2n-1，同时在前面加上了一些数，删去了一些数，具体的：
4 6 9 10 11 13 14 15 17 19 21 23 25
8 10 11 12 13 14 15 17 18 19 21 23 25 27
其中加入了2n-1=27，删去了4,6,9，加入了8,12,18，发现加入的数是对应删去的数的二倍，并且通过观察一些变化，我们发现删去的数与2n-1的因数有关，进一步的我们发现，在加入数27时，27在前面的数中有其的一个因数9，9被删去了，加入了18，然后18在前面有因数6，6被删去了，加入了12，12有其因数4,4被删去了，加入了8，8在前面没有因数了，结束。
发现规律了，每次是加入2n-1，然后执行一个\mathrm{solve}(2n-1)，\mathrm{solve}(x)表示加入x所需要进行的操作，直接枚举x的因数\mathrm{fac}，每次删除\mathrm{fac}，加入2\mathrm{fac}，然后递归处理\mathrm{solve}(2\mathrm{fac})即可。
复杂度：O(n\log n)
原题： 排队
赛时做法： 最唐诗的一集，一直以为是数学题，得知\mathrm {nst}做出后还是继续想数学做法，最终在数学的道路上一去不复返。
正解：
{\large \mathrm {DP}!}
发现\mathrm{dp}队伍的长度好做
考虑f_{i,0/1}表示队伍长度为i且最后一个排上队的人是男生/女生时的排队时间总和，g_{i,0/1}表示队伍长度为i且最后一个排上队的人是男生/女生时的排队方案数总和。
有转移：
f_{i,0}\leftarrow f_{i-A,0}+f_{i-B,1} \\
f_{i,1}\leftarrow f_{i-B,0}+f_{i-C,1} \\
g_{i,0}\leftarrow g_{i-A,0}+g_{i-B,1} \\
g_{i,1}\leftarrow g_{i-B,0}+g_{i-C,1} \\
f_{i,0}\leftarrow D\times g_{i,0} \\
f_{i,1}\leftarrow E\times g_{i,1}
时间复杂度O(n)，有\mathrm{50pts}
考虑优化，发现A,B,C\le 30，所以转移点i-A,i-B,i-C和i的距离不会超过30，考虑矩乘优化，记m=\max(A,B,C)，则将连续的m个状态放在一起，即可覆盖所有的转移点。
但注意此题的矩阵规模有30\times 4=120，要仔细考虑如何构造矩阵。考虑构造：
\begin{bmatrix}
f_{i,0} & \dots & f_{i+m-1,0} & f_{i,1} & \dots & f_{i+m-1,1} & g_{i,0} & \dots & g_{i+m-1,0} & g_{i,1} & \dots & g_{i+m-1,1}
\end{bmatrix}
转移到
\begin{bmatrix}
f_{i+1,0} & \dots & f_{i+m,0} & f_{i+1,1} & \dots & f_{i+m,1} & g_{i+1,0} & \dots & g_{i+m,0} & g_{i+1,1} & \dots & g_{i+m,1}
\end{bmatrix}
容易构造转移矩阵
矩乘优化，做完了，复杂度O((4\max(A,B,C))^3\log n)=O(m^3\log n)
原题： 道路
赛时做法： 我有一个绝妙的解题性质，但是这比赛时间太少，我想不出来。
正解：
性质：每次选择的作为首都的点一定是出度最大的点，且这个点到其他点的最大距离不超过2
先求出答案的下界，选择u作为首都，记u的出度为d_u，那么u可以直接到达的点的个数就是d_u，我们要求答案的下界，所以直接假设u不能直接到达的点到u的距离都是2，那么答案的下界就是
d_u+2(n-d_u-1)=2n-2-d_u
明显此时我们取到d_u最大的点答案最小，下面我们可以证明选择出度最大的点答案就是2n-2-d_u
反证法
假设选择出度最大的点会有点与其距离大于2，
假设出度最大的点为u，有一个与其距离大于2的点为v
如图，我们可以发现此时点v一定有边指向u及其所有的出点，否则到v的距离就是1或2了，于是此时我们发现v的出度至少是d_u+1，这与u是出度最大的点相矛盾，所以选择出度最大的点，与其距离最远的点的距离不会超过2
于是我们只需要维护出度最大的点，记为u，那么答案就是2n-2-d_u
原题： A. 【PR #15】最小表示法/Minimal Cyclic Shift
/P3830
赛时做法： 并没有想到如何求出f(s)为一个值时的字符串个数，打了个n\le 5,a_i\le 5的表，暴力拿了\mathrm {15pts}
正解：
记pos_i表示i在写错后的位置，可以发现最后要求出
E(\sum_{i=1}^n [f(s_{pos_i})=f(s_i)]) \\
=\sum_{i=1}^n E([f(s_{pos_i})=f(s_i)]) \\
=\sum_{i=1}^n P(f(s_{pos_i})=f(s_i))
考虑计算出f(s_i)=k的概率，我们从字符串周期的角度进行考虑，假设s_i的循环节长度为d，我们发现一个重要的结论，k\le d时有P(f(s_i)=k)=\frac{1}{d}，k>d时有P(f(s_i)=k)=0。
首先可证k>d时一定不行,因为此时如果k可以作为最小表示法的循环表示，那么此时(k-d)也一定是最小表示法的循环表示，这样我们找到小于k然后同样可行的，根据f的定义此时k一定不是最小表示法的循环表示。
当k\le d时，可以观察到这个循环节中每个点作为f(s_i)的次数是相同的，所以每个点作为f(s_i)是等概率的，于是k\le d时有P(f(s_i)=k)=\frac{1}{d}
而计算一个长度为i的循环节的个数g_i是简单的，有递推式：
g_i=26^i-\sum_{j|i}g_j
所以可以计算出
P(f(s_i)=k)=\sum_{d|a_i\wedge k\le d}\frac{g_d}{d}
记res(i,j)表示f(s_i)和f(s_j)相同的概率，那么答案就是\sum_{i=1}^{n}res(i,pos_i)，
枚举f(s_i)=f(s_j)=k，有
res(i,j)=\frac{1}{26^{a_i}26^{a_{j}}}\sum_{k}P(f(s_i)=k)P(f(s_{j})=k) \\
=\frac{1}{26^{a_i}26^{a_{j}}}\sum_{k}(\sum_{d|a_i\wedge d\ge k}\frac{g_d}{d}\times \sum_{d|a_j\wedge d\ge k}\frac{g_d}{d}) \\
记a_i的因数数组为dx，a_j的因数数组为dy，后面的求和可以进行转化
\sum_{k}(\sum_{dx_d\ge k}\frac{g_d}{d}\times \sum_{dy_d\ge k}\frac{g_d}{d})
观察这个式子发现可以将dx,dy排序后双指针扫描，而因数数组可以通过预处理
最终复杂度O(n\sqrt{V})
原题：树套树
赛时做法： 试图拆贡献失败，想到了一个\mathrm {dp}结果复杂度假掉了，最终成为暴力选手
正解：
还是拆贡献
将所有的T看成一个大点，那么两点之间的路径可以简化成如下的情况：
考虑拆贡献计算
对于绿色的边，即连接大点之间的边，贡献显然为n\times n=n^2，即左边选一个点，右边选一个点
对于蓝色的边，即连接T中一个点到T的一个"出口"的一条边，可以看作是从T的一个出口到其他点的距离和，计算也是简单的，直接树形\mathrm {dp}预处理T中每个点到其他点的距离和即可
关键是红色的边，即连接T中一个出口到另一个出口的一条边，可以发现对于一个T，用w_u表示出口u连出去的点的个数，于是贡献可以表示为\sum_{i,j}dist(i,j)w_iw_j，其中i,j枚举T中的出口。这个东西对于每个T还是不同的，考虑使用虚树的技巧处理。
于是最终复杂度O(n\log n)
原题： P6860
正解：
先考虑从(0,0)出发能到达所有点的条件是什么
首先我们不需要考虑下标为负数的，因为如果能走到(x,y)，那么将每一步的对称走法走一下就可以走到(-x,-y)
并且只要我们能在任意一格(x,y)走到(x+1,y)和(x,y+1)，那么就可以到达所有的非负点，进而可以到达所有点，这相当于可以从(0,0)到达(1,0)和(0,1)就行了，但是我们进一步发现只要能到达(1,0)就行了，因为根据马的走法只需要将在横坐标上走的和纵坐标上走的调换一下就可以走到(0,1)
于是问题转化为，p(a,b)表示是否能从(0,0)到达(1,0)
将走法分为用(\pm a,\pm b)走，然后用(\pm b,\pm a)走，对于两部分，由于a和b中走一个其中另一个也走，所以我们可以发现a走的贡献系数和b走的贡献系数一定是同奇偶的
于是第一部分可以走到的点可以表示为(2x_1a,2x_2b)或((2x_1+1)a,(2x_2+1)b)，第二部分可以走到的点可以表示为(2x_3b,2x_4a)或((2x_3+1)b,(2x_4+1)a)
所以可以分类讨论，列下四个方程组:
\left\{\begin{matrix}
2x_1a+2x_3b=1 \\
2x_2b+2x_4a=0
\end{matrix}\right. \\
\left\{\begin{matrix}
2x_1a+(2x_3+1)b=1 \\
2x_2b+(2x_4+1)a=0
\end{matrix}\right. \\
\left\{\begin{matrix}
(2x_1+1)a+2x_3b=1 \\
(2x_2+1)b+2x_4a=0
\end{matrix}\right. \\
\left\{\begin{matrix}
(2x_1+1)a+(2x_3+1)b=1 \\
(2x_2+1)b+(2x_4+1)a=0
\end{matrix}\right. \\
首先根据裴蜀定理a,b一定满足\gcd(a,b)=1,然后可以解得a为偶，b为奇或者a为奇，b为偶，即a\bmod 2=0\wedge b\bmod 2=1或a\bmod 2=1\wedge b\bmod 2=0
于是推柿子
\sum_{i=1}^{n}\sum_{j=1}^{n}p(i,j) \\
=2\sum_{i=1}^{n}\sum_{j=1}^{i}p(i,j) \\
记 s_1(n)=\sum_{i=1}^{n}\sum_{j=1}^{i}[i\bmod 2=0][j\bmod 2=1][\gcd(i,j)=1] \\
记 s_2(n)=\sum_{i=1}^{n}\sum_{j=1}^{i}[i\bmod 2=1][j\bmod 2=0][\gcd(i,j)=1] \\
由于偶数和偶数一定不互质，所以
s_1(n)=\sum_{i=1}^{n}\sum_{j=1}^{i}[i\bmod 2=0][\gcd(i,j)=1] \\
=\sum_{i=1}^{n}[i\bmod 2=0]\varphi(i)
对于s_2(n)，由于\gcd(n,x)=\gcd(n,n-x)，所以\gcd(n,x)=1\to \gcd(n,n-x)=1
考虑计算与奇数i互质的偶数的个数，假设一个偶数x满足\gcd(i,x)=1，那么可以得到\gcd(i,i-x)=1，而由于i为奇数,x为偶数，所以i-x为奇数，这样我们可以将每一个与i互质的偶数映射到一个与i互质的奇数，所以与i互质的偶数占与i互质的数的一半，即\frac{\varphi(i)}{2}
所以
s_2(n)=\sum_{i=1}^{n}[i\bmod 2=1]\frac{\varphi(i)}{2}
于是答案为：
2(s_0(n)+s_1(n))-1 \\
=2\left(\sum_{i=1}^{n}[i\bmod 2=0]\varphi(i)+\sum_{i=1}^{n}[i\bmod 2=1]\frac{\varphi(i)}{2}\right )-1 \\
=2\sum_{i=1}^{n}[i\bmod 2=0]\varphi(i)+\sum_{i=1}^{n}[i\bmod 2=1]\varphi(i)-1
其中减1是因为\varphi(1)应是没有贡献的，但是多计算了，应该减去
可以考虑定义
\mathrm {solve}(n)=2\sum_{i=1}^{n}[i\bmod 2=0]\varphi(i)+\sum_{i=1}^{n}[i\bmod 2=1]\varphi(i) \\
=\sum_{i=1}^{n}[i\bmod 2=0]\varphi(i)+\sum_{i=1}^{n}[i\bmod 2=0]\varphi(i)+\sum_{i=1}^{n}[i\bmod 2=1]\varphi(i) \\
=\sum_{i=1}^{n}[i\bmod 2=0]\varphi(i)+\sum_{i=1}^{n}\varphi(i)
考虑前面一部分怎么算，根据\varphi的性质，假设x为1到n中的一个偶数，那么当\frac{x}{2}为奇数时，有\varphi(i)=\varphi(\frac{i}{2})，否则有\varphi(i)=2\varphi(\frac{i}{2})，这恰好与\mathrm {solve}的计算吻合，即2倍偶数位和1倍奇数位的和，所以
\mathrm {solve}(n)=\mathrm {solve}\left(\frac{n}{2}\right)+\sum_{i=1}^{n}\varphi(i)
直接杜教筛即可
最终答案：\mathrm {solve}(n)-1
原题： 公交(bus)
给定长度为n的数列d,m，要求求出
\min_{i=1}^{n}\{\left(\sum_{j=1}^{i}d_j\right)+w_iv\}
进行q次询问，每次单点修改d_p或m_p为f，并给定v，求出式子的值
n,q\le 10^5$，值域$10^9
赛时做法： 以为可以使用广义矩乘，但是发现式子无法用矩乘做，最终暴力+部分分60\mathrm{pts}，\texttt{nst}赛时想到凸包上二分\mathrm{orz}, \texttt{nst} 太强大了！
正解：
将和转化成前缀和，于是要求
\min_{i=1}^{n}\{{sum_i}+m_iv\}
先考虑静态如何求，这个式子与直线的斜截式类似，考虑转化成凸包
将sum_i+m_iv化成sum_i-(-v)m_i，然后将sum_i视为y，(-v)视为k，m_i视为x，然后原式变成y-kx，这时我们要找这个式子的值就相当于y-kx=b中的b，即用一个斜率为k的直线去截这个点，得到的截距的值
据此，我们想到了维护凸包，将(m_i,sum_i)作为一个点，按m_i从小到大排序后，从前到后维护，求出这些点的下凸包
查询时，在凸包上二分，拿斜率为(-v)的直线去截
这样我们就解决了静态的问题
而对于有更改的，单点修改d_p=f相当于让[p,n]的后缀中的sum全部加上f-d_p，单点修改m_p=f相当于m_p加上f-m_p，于是要支持区间加、单点加，考虑用分块。
对于每个块维护一个凸包，区间加使用\mathrm{add}懒标记，是简单的，最后对于每个块的答案加上\mathrm{add}[b]即可，单点加就直接在块中找到这个下标，加上，类比插入排序将这个修改后的数正确排序回去即可
设块长为B，于是块数为\frac{n}{B}
一次修改复杂度：O(B+\frac{n}{B})
一次查询复杂度：O(\frac{n}{B}\log {B})=O(\frac{n}{B}\log n)
于是列出：B+\frac{n}{B}=\frac{n}{B}\log n
B^2+n=n\log n
取B=\sqrt{n\log n}
总复杂度：m\sqrt{n\log n}
原题： loser
赛时做法： 写了一个唐诗O(n^5)的\mathrm {dp}，没有发现可以结合贪心，直接沦为暴力选手
正解：
重要性质：一个点如果颜色0\to 1那么其子树中的点也一定全部变成1；一个点如果颜色1\to 0那么其到根的路径一定全部变成0。贪心易证。
于是此时整棵树会被分为三部分，即上方是全部变成0，中间一部分不变，到下方全部变成1
然后直接考虑树形背包\mathrm{dp}
定义f_{u,j,0/1/2}表示考虑以u为根的子树，使用了j次反转操作，此时的u点是到根全是0/不变/子树全是1时的最小次数
有转移：
f_{u,j+k,2}\leftarrow f_{u,j,2}+f_{v,k,2} \\
f_{u,j+k,1}\leftarrow f_{u,j,1}+\min(f_{v,k,1},f_{v,k,2})+W \\
f_{u,j+k,0}\leftarrow f_{u,j,0}+\min(f_{v,k,0},f_{v,k,1},f_{v,k,2}) \\
其中W是中间不变的一层中1产生的代价
直接转移即可，O(n^2)
原题： A.不能说的秘密
赛时做法： 想到了贪心，但是复杂度错误，刚开始写了最坏O(n^3\log n)的做法，最后终于想到O(n^2)做法，但是最后不够时间没有想到优化，遗憾\mathrm{50pts}
正解：
拜谢\texttt{lhd}以及\texttt{yjh}的题解
有显然的贪心：每一次选择t_u最小的点试图将其拿走
然后考虑如何优化，对于一个点，必须要取走其父节点才能选它本身的限制很难处理，考虑如何通过转化取消这个限制，我们发现一个结论：令
t_u\leftarrow \min_{v\in son(u)}t_v
可以发现这是不会对答案造成影响的，然后此时t就会随着往上而单调递减，所以考虑u的子树时，由于要优先操作t更小的，所以一个点一定不会比其父节点更早操作，所以此时直接按照t从小到大的顺序做，假设u子树中t已经排序，那么答案显然是：
\min_{i=1}^{\mathrm{SZ}(u)}(t_{son_i}-i+1) \\
=\min_{i=1}^{\mathrm{SZ}(u)}(t_{son_i}-i)+1
考虑这个怎么快速做
由于要对t进行排序，考虑使用权值线段树，在值域上维护两个信息\mathrm{sz,mi}，表示值域中数的个数以及当前值域中原\min柿子的值，然后用线段树合并做即可。
时间复杂度：O(n\log n)
原题： P7907 [Ynoi2005] rmscne
正解：
设原序列为a
考虑离线询问，然后扫描线
假设当前扫描到以r作为右端点的，我们考虑求出一个nxt_{l^\prime}表示[l^\prime,nxt_{l^\prime}]是满足条件的长度最短的子区间，先考虑求出nxt
当前扫描到r，那么相当于加入了a_r，根据经典套路，考虑a_r上一次出现的位置，记为pos_{a_r}，这时我们发现，[pos_{a_r}+1,r]中唯一的a_r就出现在r的位置，因此对于l^\prime\in[pos_{a_r}+1,r]，由于要包含a_r，并且唯一的a_r在r的位置，所以有nxt_{l^\prime}=r，所以相当于每次将[pos_{a_r}+1,r]中的nxt都覆盖成r，这个用线段树做是简单的
然后考虑如何使用这个nxt对于区间[l,r]求出答案，首先，我们发现只要求出最大的p满足[p,r]是满足条件的，那么答案就是
\min_{l^\prime\in[l,p]} (nxt_{l^\prime}-l^\prime+1)
然后问题变成如何求出最大的p满足[r,p]满足条件
考虑一个很巧妙的方法，开一个并查集，并查集中i的祖先p_i存储p\in[i,r]并且使得[p,r]满足条件的最大的p，然后扫描到r时，由于加入了a_r，考虑经典套路，此时[pos_{a_r}+1,r]中就有一个a_r了，所以此时pos_{a_r}处就没有用了，往右移并不会影响其满足条件，所以让pos_{a_r}和pos_{a_r}+1连边，即令p_{pos_{a_r}}=pos_{a_r}+1
然后我们只需要维护(nxt_{l^\prime}-l^\prime+1)的区间最小值即可，线段树直接做
然后O(n\log n)解决问题