CF678(EDU13) 题解 / 李超线段树学习笔记

zrl123456 · 2025-09-03 23:02:24 · 题解

:::::info[闲话] 记 a,b,c,d,e,f 为我分别在 A,B,C,D,E,F 上花的时间，那么 a+b+c+d+e<f。
:::::

A. Johny Likes Numbers：

:::::info[题目基本信息] 考察：数学（\color{#FE576A}800）。
题目简介：
给你两个正整数 n,k，求一个最小正整数 x 满足：

1. k|x
2. x>n

数据范围：

• 1\le n,k\le 10^9

  ::::: 容易发现这个 x 的前一个被 k 整除的数 y 就是 y\le n 时的最大值，那么最后答案就是：

  \begin{aligned}x&=y+k\\&=\frac{y}{k}\cdot k+k\\&=(\frac{y}{k}+1)k\\&=(\lfloor\frac{n}{k}\rfloor+1)k\end{aligned}

  时空复杂度均为 \Theta(1)。

  B. The Same Calendar：

  :::::info[题目基本信息] 考察：数学（\color{#FFC116}1600）。
  题目简述：
  给你一个年份 y，求下一个年份 y'，使得这两年的日期在日历上的排布相同。
  数据范围：

• 1000\le y<100000

  ::::: 容易发现，两年的日期在日历上的排布相同的充要条件是：

• 两年天数相同。
• 两年第一天的星期几相同。

第一个条件直接根据平年和闰年的定义判断即可，第二个条件需要进行转化：
设这一年的第一天为星期 X（为了方便，我们设星期天为星期 0，也就是说此处 X\in[0,6]），那么符合条件的下一年也应为星期 X，设此时一共过了 Y 天，也就是说：

即：

所以，我们直接从这一年开始，暴力向下枚举即可。
容易发现两年不会隔太远。
:::::success[证明] 容易发现，平年天数 365\bmod7=1，闰年天数 366\bmod7=2，我们不妨以 4 年为一整体，那么含闰年的整体天数对 7 取模的余数为 5，不含的余数为 4，且根据闰年定义，4 与 4 之间相隔二十多个整体。
那么如果全是 5，循环 7 次即可；如果有一个 4，最多循环十几次。所以不可能出现两个 4。
证毕。
::::: 时空复杂度均为 \Theta(1)。

C. Joty and Chocolate：

:::::info[题目基本信息] 考察：数学，贪心（\color{#FFC116}1600）。
题目简介：
有一列长度为 n 的地砖，编号为 1 到 n，编号是 a 的倍数的可以涂成红色并获得 p 的价值，编号是 b 的倍数的可以涂成蓝色并获得 q 的价值，一个地砖只能涂成一种颜色，问最大价值是多少。
数据范围：

• 1\le n,a,b,p,q\le 10^9

  ::::: 容易发现若一个地砖的编号既是 a 的倍数，又是 b 的倍数，那么它肯定会被涂成价值更大的颜色。
  所以我们不妨钦定 p\ge q，不然我们直接交换颜色。
  此时涂成红色显然更优，所以有 \displaystyle\lfloor\frac{n}{a}\rfloor 的地砖会涂成红色，剩下的地砖中未被涂色的 \displaystyle\lfloor\frac{n}{b}\rfloor-\lfloor\frac{n}{\text{lcm}(a,b)}\rfloor 个地砖会被涂成蓝色，那么最后答案就是：

  \lfloor\frac{n}{a}\rfloor\cdot p+(\lfloor\frac{n}{b}\rfloor-\lfloor\frac{n}{\text{lcm}(a,b)}\rfloor)\cdot q

  时空复杂度均为 \Theta(1)。

  D. Iterated Linear Function：

  :::::info[题目基本信息] 考察：矩阵快速幂（\color{#52C41A}1700）。
  题目简介：
  定义函数 f(x)=Ax+B，定义函数 g^{(n)}(x) 为：

  g^{(n)}(x)=\begin{cases}x&n=0\\f(g^{(n-1)})&\text{otherwise}\end{cases}

  求 g^{(n)}(x) 的值对 10^9+7 取模的结果。
  数据范围：

• 1\le A,B,x\le 10^9
• 1\le n\le 10^{18}

  ::::: 容易发现，n 的数据范围过大，无法支持 \Theta(n) 的时间复杂度，所以我们考虑优化。
  对于这种递推方程式，除了直接化简就是采用矩阵加速，在此题中两种方法均可，下面是矩阵加速的方法，因为它思维量少（……真的吗？）。
  我们注意到，在递推式 g^{(n)}(x)=f(g^{(n-1)}(x))=Ag^{(n-1)}(x)+B 中有两个单项式，分别是 g^{(n-1)}(x) 和 B，那么我们开矩阵存的就是他们。 那么最初始矩阵就为：

  \begin{bmatrix}g^{(n-1)}(x)\\B\end{bmatrix}

  现在我们要得到：

  \begin{bmatrix}g^{(n)}(x)\\B\end{bmatrix}

  假设要乘的矩阵为 base，那么我们得到：

  base\times\begin{bmatrix}g^{(n-1)}(x)\\B\end{bmatrix}=\begin{bmatrix}g^{(n)}(x)\\B\end{bmatrix}

  容易得到：

  base=\begin{bmatrix}A&1\\0&1\end{bmatrix}

  根据矩阵乘法的结合律会得到最终答案矩阵 ans 就为：

  ans=\begin{bmatrix}A&1\\0&1\end{bmatrix}^n\times\begin{bmatrix}x\\B\end{bmatrix}

  答案就是 ans 的左上角元素。
  时间复杂度为 \Theta(\log n)，空间复杂度 \Theta(1)。

  E. Another Sith Tournament：

  :::::info[题目基本信息] 考察：状压 DP（\color{#52C41A}2200）。
  题目简介：
  有 n 个人在进行 n-1 轮比赛，每轮有两个人进行斗争，败者淘汰，胜者在擂台上与下一轮的另一人斗争。已知第 i 个人与第 j 个人斗争时第 i 个人获胜的几率是 a_{i,j}，问第 1 个人在可以排布比赛顺序的情况下他获胜的最大概率是多少。
  数据范围：

• 1\le n\le 18
• \forall i,j\in[1,n],0\le a_{i,j}\le 1
• \forall i\in[1,n],a_{i,i}=0
• \forall i,j\in[1,n],i\ne j,a_{i,j}+a_{j,i}=1

  ::::: :::::info[闲话] 听说这题后来被贪心爆标了。
  ::::: 注意到 1\le n\le 18，那么我们考虑状压 dp。
  先设 f_p 为场上存活状态为 p 的概率时第 1 个人获胜的概率。
  但是这样设状态会有 bug，所以我们设 f_{p,i} 为场上存活状态为 p 且擂台上是第 i 个人时第 1 个人获胜的概率。 :::::success[对于状态设计的一点说明] 其实设 f_{p,i} 为参与过争斗状态为 p 且擂台上是第 i 个人时第 1 个人获胜的概率也可以，但是参与过争斗的状态、擂台上的人、存活状态知二求一，所以这两种其实等价。
  ::::: 然后我们发现如果 p 从大往小推时，1 淘汰时不好处理边界，所以我们令 p 从小往大推。
  最开始令 f_{\{1\},1}\leftarrow1。
  然后我们容易得到状态转移方程：

  f_{p,i}=\max_{j\in p,j\ne i}(f_{\complement_p\{j\},i}\cdot a_{i,j}+f_{\complement_p\{i\},j}\cdot a_{j,i})

  最后答案就为：

  \max_{i=1}^n(f_{\bigcup_{j=1}^n\{j\},i})

  时间复杂度为 \Theta(2^nn^2)，空间复杂度为 \Theta(2^nn)。

  F. Lena and Queries：

  :::::info[题目基本信息] 考察：动态开点，李超线段树，计算几何（\color{#9D3DCF}2500）。
  题目简介：
  有 3 种 n 个操作，分别是：

  1. 向集合 S 中加入数对 (x,y)。
  2. 删除集合 S 中在第 k 次操作加入的数对。
  3. 给定 k，求 \displaystyle\max_{(x,y)\in S}(kx+y)。

数据范围：

• 1\le n\le 3\times 10^5

  ::::: 容易发现，如果没有操作 2 就是李超线段树板子，但是现在有操作 2 了李超线段树就做不了了，同时我们也不想上几乎万能但超级难写的平衡树，怎么办呢？
  注意到这道题比李超线段树板子少了一个强制在线的限制，所以我们考虑离线下来。
  离线下来之后莫队显然时间复杂度不理想，再加一个李超线段树板子维护就是 \Theta(n\sqrt n\log n)，不太能跑。
  那么我们考虑对操作编号开一棵线段树，对于每个数对容易维护他们出现的区间，在线段树上跑给 \Theta(\log n) 个点挂上数对，然后在这一个点上开一棵动态开点的李超线段树，对于不同值域维护答案即可。
  对于操作 3，我们可以直接找到此时的操作对应的叶子结点，不断往上蹦不断查询即可。
  时间复杂度为 \Theta(n\log^2n)，空间复杂度为 \Theta(n\log n)。 :::::warning[坑点] 由于此做法空间复杂度为 \Theta(n\log n) 且空间常数较大，所以要关 long long，只在统计答案时开 long long，同时也不要在节点内存 l 和 r，节约空间。
  :::::