2021.1做题记录

## CF700E Cool Slogans **description** 给定字符串 $S$，要求构造字符串序列 $s_1,s_2\cdots s_k$，使得 $s_i$ 在 $s_{i+1}$ 中至少出现了两次，并且 $s_i$ 都是 $S$ 的子串，求最大的 $k$ **solution** 在最优情况下，$s_i$ 一定是 $s_{i+1}$ 的后缀 所以首先对于 $S$ 建出 SAM，线段树合并出 right 集合 因为 SAM 上一个状态的所有字符串等价，所以只需要考虑每个点最长的那个 在 parent tree 上 dp，用 $f[i]$ 表示 $i$ 节点表示的状态 $k$ 最大是多少 那么转移有 $f[i]=\max\{f[j]+1\}$，$j$ 为 parent tree 上 $i$ 的祖先，其中 $j$ 的 right 集合中在 $[pos[i]-len[i]+len[j],pos[i]-1]$ 上有点 注意不能判断 $[pos[i]-len[i]+len[j],pos[i]]$ 上有两点，因为克隆出来的点会重复算 显然这个 dp 满足单调性，可以倍增做到两个log，也可以记录转移节点做到一个 log [code](https://www.luogu.com.cn/record/44494257) ## CF605E Intergalaxy Trips **description** 现在有 $n$ 个点的有向完全图，边 $(i,j)$ 出现的概率是 $p_{i,j}$，$p_{i,i}=1$，问从 $1$ 到 $n$ 的最短路的期望长度 假设这个人足够聪明 $n\leq 1000$ **solution** 这道题因为这个人足够聪明，所以他可以对于一个情况动态的做出决定 因为正着推不太好确定还需要几步能到，所以我们考虑从 $n$ 倒着推，设 $E_i$ 表示从 $i$ 走到 $n$ 的答案 考虑 $E_i$ 的计算，对于 $E_i$ 的所有出边 $j$ ，显然只有当所有的 $E_k<E_j$ 的 $(i,k)$ 都没有出现的时候，我们才会考虑往 $j$ 走。所以我们可以推出一个转移 $$E_i=\sum_{j=1}^nE_j\times p_{i,j}\times \prod_{k}^{E_k<E_j}(1-p_{i,k})$$ 但是这个转移是有问题的。 因为可能存在一个情况，使得这个时候 $i$ 没法走到其他的地方，这样的情况出现的概率是 $\prod_{j}(1-p_{i,j})$，但是这个时候因为 $E_i$ 只计算的是非自环上的期望，所以转移应该写成 $$E_i=\sum_{j=1}^n\dfrac{E_j}{1-\prod_{k=1}^n (1-p_{j,k})}\times p_{i,j}\times \prod_{k}^{E_k<E_j}(1-p_{i,k})$$ 考虑转移的顺序，显然在更新的时候，如果存在一个 $E_k<E_j$，并且还没有向那里走过，那么我们应该优先从 $i$ 往 $k$ 走。 所以我们可以每次枚举最小的之前没有更新过的 $E_j$ 更新 这个做法和朴素的 $\mathcal O(n^2)$ dijkstra 类似 [code](https://www.luogu.com.cn/record/44513594) ## CF908D New Year and Arbitrary Arrangement **description** 给定 $n,pa,pb$ 每次有 $\dfrac{pa}{pa+pb}$ 的概率在后面增加一个 `a` 每次有 $\dfrac{pb}{pa+pb}$ 的概率在后面增加一个 `b` 当字符串里面有大于等于 $n$ 个 `ab` **子序列** 时停止 问 `ab` **子序列** 的期望个数 $n\leq 1000$ 对于 $10^9+7$ 取模 **solution** 发现 `b` 开头的情况不会对答案造成影响 所以钦定第一个是 `a` 我们用 $f[i][j]$ 表示有 $i$ 个 `a`，一共现在有 $j$ 个 `ab` 子序列的方案数 那么 $f[i][j]\to f[i+1][j],f[i][j]\to f[i][i+j]$ 考虑做到 $i,j\leq n$，所有 $i+j\geq n$ 的，对于答案的贡献就是 $(i+j)\times f[i][j]$ 还有一部分，是已经有 $n$ 个 `a`，但是依然没有凑够 $n$ 个 对于这一部分，我们发现他们是可以无限延伸的，$f[n][m]$ 对于答案的贡献就是 $$f[n][m]\times \sum_{i=0}^{\infty}(n+m+i)pa^ipb$$ 那么现在的瓶颈在于求后面那个东西，利用类似于等比数列的方法，我们可以推出来 $$\sum_{i=0}^\infty(n+m+i)pa^ipb=n+m+\dfrac{pa}{pb}$$ 这样的话我们就可以在 $\mathcal O(n^2)$ 的时间里求出答案了 [code](https://www.luogu.com.cn/record/44527798) ## CF578D LCS Again **description** 给定一个字符串 $S$，问有多少个与 $S$ 等长的字符串 $T$，使得 $S,T$ 的最长公共子序列长度为 $|S|-1$，并且 $S,T$ 均由前 $m$ 个小写字母组成 $n\leq 10^5$ **solution** 首先考虑一个位置，可以删掉，填上与他相异的任意一个字符，一共有 $n\times n\times (m-1)$ 种 但是显然会出问题 比如说样例1，`aa` 这种连续两个重复的，显然第二个 `a` 就不用算到了 但是这样还是有重复的问题，比如说第二个样例，我们发现，`ab` 这种类型的出现之后，我们发现，如果我们把 `a` 删掉之后，如果换成 `b`，那么放在 `b` 的左边和 `b` 的右边本质上来说就是一样的了 所以对于 `ab` 这种的串，我们也需要考虑 同样的，对于 `abababababab` 这种的，我们需要放在一起考虑 显然这个时候重复的串的个数是 $len\times(len-1)/2$ 这样的话我们就可以找到全部的了 $\mathcal O(n)$ [code](https://www.luogu.com.cn/record/44570237) ## P4027 [NOI2007] 货币兑换 **description** [link](https://www.luogu.com.cn/problem/P4027) **solution** 用 $f[i]$ 表示在第 $i$ 天最多可以赚多少钱 用 $geta[i],getb[i]$ 第 $i$ 天可以换多少 A 和 B 有一个显然的转移方程 $$f[i]=\max\{A[i]\times geta[j]+B[i]\times getb[j]\}$$ 显然这个东西不太好搞 所以我们转化一下 $$f[i]=B[i]\times\max\{\dfrac{A[i]}{B[i]}\times geta[j]+getb[j]\}$$ 显然这个东西可以斜率优化 但是发现斜率 $-\dfrac{A[i]}{B[i]}$ 和 $x$ 坐标 $geta[j]$ 不单调 **sol ver.1** 所以我们需要平衡树维护这个上凸壳 复杂度 $\mathcal O(n\log n)$ [code ver.1](https://www.luogu.com.cn/record/44621491) **sol ver.2** 我们换一种斜率优化的思路 看成若干条 $y=geta[j]x+getb[j]$ 在 $A[i]$ 点处的最大值 可以离散化后李超线段树维护 复杂度 $\mathcal O(n\log n)$ [code ver.2](https://www.luogu.com.cn/record/44640619) **sol ver.3** 我们考虑 CDQ 分治 首先对于 $-\dfrac{A[i]}{B[i]}$ 排序 然后对于时间分治。 对于左半部分，我们把它按照 $x$ 坐标排序，然后我们把左边的凸包维护出来，然后对于右半部分因为斜率是单调的，所以我们可以线性的查找 然后对于 $x$ 坐标归并就可以了 复杂度 $\mathcal O(n\log n)$ [code ver.3](https://www.luogu.com.cn/record/44644059) 实际上来看CDQ跑的最快，李超最好写，平衡树比较好想（如果不会李超的话） ## P2305 [NOI2014] 购票 **description** [link](https://www.luogu.com.cn/problem/P2305) **solution** 用 $f[i]$ 表示从 $i$ 走到 $1$ 最少花费的钱数 显然有转移 $$f[i]=\min\{f[j]+(dis[i]-dis[j])\times p[i]+q[i]\}$$ 发现就是一个树上的斜率优化。 树上斜率优化的方法主要有这些： **sol ver.1** 树上斜率优化可以淀粉质来实现。 我们找到树的重心，把重心的子树割掉之后继续求答案。 然后用重心到 $rt$ 的路径上的所有点更新重心的子树里面的答案。 更新的时候，对于重心的子树里面的点，我们把他们按照 $dis-l$ 从大到小排序，这样我们每次只需要往凸包中加入一个点。 求最优值的时候再凸壳上二分即可 淀粉质的时候，最多有 $\mathcal O(\log n)$ 层，每层处理的时候需要 $\mathcal O(n\log n)$ 的时间，总复杂度为 $\mathcal O(n\log^2n)$ [code ver.1](https://www.luogu.com.cn/record/44686601) ## P4022 [CTSC2012]熟悉的文章 **description** 给定 $m$ 个模板串 $\{T_i\}$，$n$ 次询问，每次给定一个串 $S$ 求最大的 $L$，使得可以把 $S$ 划分成若干段，使得“是任意一个模板串的子串，并且长度 $\geq L$” 的段数的长度之和 $\geq 90\% |S|$ 输入文件总长不超过 $1.1\times 10^6$ **solution** 显然 $L$ 可以二分 我们用 $f[i]$ 表示将 $i$ 位置作为一段的结尾的“是任意一个模板串的子串，并且长度 $\geq L$” 的段数的长度之和。 那么显然有转移 $$f[i]=\max\{f[j]+i-j\},j\in[i-maxlen[i],i-L]$$ 其中 $maxlen[i]$ 表示 $i$ 往前最多可以延伸多少位，使得他是一个 $T_i$ 的子串 这个东西我们只需要用 $S$ 在模板串的广义 SAM 上跑匹配就可以了 此时复杂度是 $\mathcal O(n^2\log n)$ 同时注意到，$i-maxlen[i]$ 显然是具有单调性的 所以我们可以单调队列优化 复杂度 $\mathcal O(n\log n)$ [code](https://www.luogu.com.cn/record/44731489) ## P3749 [六省联考2017]寿司餐厅 **description** [link](https://www.luogu.com.cn/problem/P3749) **solution** 显然，如果我们选了 $d_{i,j}$，那么 $d_{i+1,j}$ 和 $d_{i,j-1}$ 我们都需要选 所以问题转化成了一个最大闭合子图问题 $d_{i,j}$ 向 $d_{i+1,j}$ 和 $d_{i,j-1}$ 连容量 inf $d_{i,i}$ 向 $i$ 连 inf $i$ 向 $a_i$ 连边 然后相应的按照最大闭合子图的建边方法连边就好了 复杂度玄学 [code](https://www.luogu.com.cn/record/44801149) ## CF444E DZY Loves Planting **description** [link](https://www.luogu.com.cn/problem/CF444E) **solution** 口胡了一个二分+网络流的做法，不知道为啥没过（ 考虑把所有的边从小到大排序，然后用并查集进行合并 对于每一个连通块维护一个 $siz$ 表示点的个数， $val$ 表示 $x$ 的和 那么对于每个连通块，我们都要对他外面的一些点进行匹配 所以如果 $siz\leq sumx-val$ 就可以，否则不行 $\mathcal O(n\alpha(n))$ [code](https://www.luogu.com.cn/record/44925238) ## CF773E Blog Post Rating **description** 给定一些数，你需要把他们按照任意顺序排好一个数列 $\{a_i\}$ 接下来执行函数 $\text{F}$ 初始 $\text F=0$ 从 $1\sim n$ 循环 若 $\text F<a_i,\text F++$ 若 $\text F>a_i,\text F--$ 问 $\text F_{max}$ $n\leq 5\times 10^5$ **solution** 显然，为了让答案更优，我们考虑把 $a_i$ 按照从小到大排序，这样可以让第一个操作执行的尽量的多 如果 $a_i>0$ 的时候，考虑按值域进行 dp，用 $f_i$ 表示处理完 $i$ 的数的答案 显然有转移： $$f[i]=\min\{f[i-1]+cnt[i],i\}$$ 转换一下写法 $$f[i]=\min\{f[i-1],i-cnt[i]\}+cnt[i]$$ 也就是 $$f[n]=\sum cnt[i]+\min\{i-\sum_{j=0}^icnt[j]\}$$ 观察发现，只要 $\text{F}<a_1$ 的时候这个 dp 都可以搞 考虑把前面部分删掉，发现应用操作2的部分一定是连续的 所以二分找到那个点，剩下的就是在权值线段树上随便搞了 $\mathcal O(n\log^2n)$ [code](https://www.luogu.com.cn/record/44953035) ## P2148 [SDOI2009]E&D **description** [link](https://www.luogu.com.cn/problem/P2148) **solution** 考虑 SG 函数 显然 $SG(x,y)=\operatorname{mex}\{SG(i,x-i),SG(i,y-i)\}$ 打表观察发现，后面那个东西相当于 $(x-1)|(y-1)$ 的二进制如果在第 $i$ 位上是 $1$，那么就有这个东西，否则没有 所以问题转化成了 $(x-1)|(y-1)$ 的二进制下第一个0 证明不会证（题解里有 [code](https://www.luogu.com.cn/record/44999530) ## CF273E Dima and Game **description** [link](https://www.luogu.com.cn/problem/CF273E) **solution** 考虑这个东西的SG函数 显然有 $SG(i)=\operatorname{mex}\{SG(i/3),SG(i-i/3)\}$ 观察发现这个 SG 直接搞会挂掉 但是他这个东西很长一段都是连续的，所以我们打表出来，然后做一个 dp 即可 [code](https://www.luogu.com.cn/record/45033134) ## CF285E Positions in Permutations **description** [link](https://www.luogu.com.cn/problem/CF285E) **solution** 还是考虑“钦定让 $i$ 个位置满足 $|p_i-i|=1$”的条件 观察发现，$i$ 为偶数和奇数的部分是相互没有影响的，所以我们分开考虑 考虑奇数部分，实际上可以理解为一些线段 $1-2,2-3,3-4$，而相邻的两条线段最多只能取一条 用 $f[i][j][0/1]$ 表示第 $i$ 条线段，选了 $j$ 条，这一条选了/没选的情况数 这样我们就可以得到整体钦定的 $f(n)$，注意 $f(i)$ 还要乘上 $(n-i)!$ 接下来进行二项式反演 $$g(m)=\sum_{i=m}^n (-1)^{i-m}\binom{i}{m}f(i)$$ 就可以得到答案啦（ 复杂度 $\mathcal O(n^2)$ [code](https://www.luogu.com.cn/record/45052387) ## CF436F Banners **description** 现在有 $n$ 个人，每个人有两个参数 $a_i,b_i$ 有两个参数 $c,p$ 对于第 $i$ 个人，如果 $b_i\geq c$，那么可以获得 $wc$ 的利润（$w$ 为一定值） 否则如果 $a_i\geq p$，那么可以获得 $p$ 的利润 现在要求对于每一个 $c$，确定利润最大的 $p$ $n\leq 10^5$ **solution** 显然可以把人按照 $b$ 排序，这样只需要按照顺序插入数据结构即可 接下来的问题是区间加等差数列，全局求 max 发现 log 数据结构不太可做，所以考虑万能的分块 每插入一个 $x$，相当于 $[1,x]$ 的出现次数都要加一 设 $cnt_i$ 表示 $i$ 在散块中被累加的次数，$k$ 表示 $i,j$ 所在的块被整体加上的次数 那么如果 $i$ 的贡献小于 $j$ ，即满足 $$cnt_i+ki<cnt_j+kj$$ 移项，可以得到 $$\dfrac{cnt_j-cnt_i}{i-j}<k$$ 可以用一个凸包维护每一块里面的内容 插入之后暴力重构一下对应点上的凸包 查询的时候每块都查询一遍取最优即可 $\mathcal O(n\sqrt n)$ [code](https://www.luogu.com.cn/record/45333119) ## CF1009F Dominant Indices **description** [link](https://www.luogu.com.cn/problem/CF1009F) **solution** 显然有一个 $\mathcal O(n^2)$ 的转移方程 $$f[u][i]=\sum f[v][i-1]$$ 发现这个复杂度是 $\mathcal O(\sum dep)$ 的 考虑长链剖分优化 长链剖分优化dp，适用于复杂度与深度相关的树形dp问题 其思路为，我们对于每个重儿子，直接继承状态，对于每个轻儿子暴力合并 这样做为什么是正确的呢，我们发现每条链都只会在链头被合并一次，总复杂度是所有链长之和，我们发现这就是 n，相应的，如果我们使用 swap 来获取重儿子上的信息，我们同样可以把空间做到线性 $\mathcal O(n)$ [code](https://www.luogu.com.cn/record/45393565) ## CF468D Tree **description** [link](https://www.luogu.com.cn/problem/CF468D) **solution** 首先第一问很好解决 答案就是 $\sum w_i\times\min(siz_i,n-siz_i)$ 考虑第二问 我们需要让我们的每一个操作都跨过一个点，这个时候肯定是最优的 显然这个点是重心 我们把重心当做根，考虑重心连出去的每一棵子树 因为要求排列的字典序尽量的小，我们从1到n考虑 对于每个点 $i$，我们要在另一棵子树里面找一个点 $j$ 所以我们找不在这棵子树里最小的那个 但是会出现一些问题，有可能某一时刻，存在一个子树 $k$，使得里面被匹配的和没被匹配的点数之和和 $n-i+1$ 相等，这个时候我们必须在子树 $k$ 里面选了，因为我们一次不能在同一棵子树里面选两个点 注意重心的特殊情况，需要特判 用一个set $S_i$ 维护子树 $i$ 中的所有没被匹配的点的集合 $low$ 维护所有 $S_i$ 中最小的集合 $num$ 维护每个子树里面还剩多少个没匹配的和没被匹配的。 $\mathcal O(n\log n)$ STL 真的恶心 [code](https://www.luogu.com.cn/record/45417745) ## CF536D Tavas in Kansas **description** [link](https://www.luogu.com.cn/problem/CF536D) **solution** 首先以S，T为起点跑一遍最短路，对于距离离散化， 然后考虑一个 dp，用 $f[0/1][i][j]$ 表示现在是先手/后手取，先手取到 $i$，后手取到 $j$ 那么 $f[0][i][j]$ 可以从 $\max\{f[0][i+1][j],f[1][i+1][j]\}$ 转移过来 $f[1][i][j]$ 可以从 $\min\{f[0][i][j+1],f[1][i][j+1]\}$ 转移过来 但是注意因为他要求必须要取到点，所以如果发现 $dis1=i+1$ 的部分没有 $dis2>j$ 的，我们必须让上一行也是他在取 倒推是因为这个dp有后效性 $\mathcal O(n^2)$ [code](https://www.luogu.com.cn/record/45461231) ## P4859 已经没有什么好害怕的了 **background** 老虚接笔了！ **description** [link](https://www.luogu.com.cn/problem/P4859) **solution** 对于 $a,b$ 从小到大排序 用 $f_{i,j}$ 表示 a 考虑到第 $i$ 个位置，钦定 $j$ 个 $a>b$ $$f[i][j]=f[i-1][j]+f[i-1][j-1]\times(low_i-j+1)$$ 其中 $low_i$ 表示 $b$ 里面有多少个比 $a_i$ 小的 最后 $f[n][i]$ 还要乘上 $(n-i)!$ 然后二项式反演一下就好了 $\mathcal O(n)$ [code](https://www.luogu.com.cn/record/45553619) ## CF449E Jzzhu and Squares **background** 毒瘤数学题 **description** [link](https://www.luogu.com.cn/problem/CF449E) **solution** 令 $n\leq m$ 考虑枚举正方形的大小 $i$，那么答案为 $$ans=\sum_{i=1}^{n}(n-i+1)(m-i+1)f(i)$$ 其中 $f(i)$ 表示所有的恰好包含在这个 $i\times i$ 的正方形中的单位正方形数量 $f(i)=i^2$ ？？？ 注意正方形可以斜着放 $$f(n)=n^2+\sum_{i=1}^{n-1}((n-2i)^2+4g(i,n-i))$$ 其中 $i$ 枚举的是旋转的量，$g(x,y)$ 表示一个 $x\times y$ 的直角三角形里面的整正方形的个数 考虑 $g(x,y)$ 的计算，相当于是求里面的整点数量+斜边整点数量，又皮克定理，我们可以得到 $$g(x,y)=\dfrac{xy-x-y+\gcd(x,y)}{2}$$ 带到原来的式子里 $$f(n)=n^2+\sum_{i=1}^{n-1}((n-2i)^2+2xy-2x-2y+2gcd(i,n))$$ （$\gcd(x,y-x)=\gcd(x,y)$） 然后把这个东西展开，问题在于求 $\sum \gcd(i,n)$ 显然有 $$\sum_{i=1}^{n-1}\gcd(i,n)=\sum_{d|n}\dfrac{n}{d}\phi(d)-n$$ 把这堆东西通通预处理出来 然后再把 $ans$ 那一层的式子继续展开，继续预处理 复杂度 $\mathcal O(n\ln n)$ [code](https://www.luogu.com.cn/record/45483727) ## CF319B Psychos in a Line **description** 显然有 $n$ 个人，每个人有一个分数 每一回合如果一个人比他右边的人分数高，他会把右边的人给杀了 每一回合杀人是同时进行的，所以一个人可以既杀了人又没杀人 被杀的人立即退出游戏 问游戏能进行几回合 $n\leq 10^5$ **solution** 显然，对于一段单调递增的区间，是不会发生任何事情的，并且只有这一段单调递增的末尾那个位置能杀人 如果把序列分成连续的每段中单调递增的几段的话 那么显然对于 $i$，他能杀的人就是后面那些段的段长的max 那么我们可以用单调栈转移一个dp 感觉不太好解释，看代码 [code](https://www.luogu.com.cn/record/45598416) ## P4770 [NOI2018] 你的名字 **background** 1k AC 祭！ **description** 给定一个串 $S$，每次询问 $T,l,r$ 表示在 $T$ 串中有多少个本质不同的子串，是的该子串不是 $S[l...r]$ 的子串 $|S|\leq 5\times 10^5$ **solution** 显然对于 $S$ 建立 SAM，然后线段树合并搞出 right 集合。 询问的时候，我们拿 $T$ 在 $S[l...r]$ 这一部分的 SAM 上跑匹配 答案就是 $\sum\{i-\max($匹配长度,T中之前和 T[1...i] 的最长公共后缀长度$)\}$ 后面那个东西我们可以对于 T 建立 SAM，在边插入的过程中求出 注意一些细节，比如说当匹配长度为 $l$ 的时候，我们需要查询的是有没有 $[L+l,R]$ 的 right集合是否不为空，而非 $[L,R]$ 以及我们不能直接跳到 $link$，应该让 $l$ 一位一位的减，因为有可能中间到一定的长度就出来了一个可以往下走的 [code](https://www.luogu.com.cn/record/45692421) ## xsy NOI2021冬令营模拟测试赛（二十五） B gre **description** 给定 $n,k$，求字典序最小的，由 $k$ 个小写字母组成的，长度为 $n$ 的，满足任意前缀出现的字母的次数相同，且任意后缀出现的字母的次数相同的字符串 $n\leq 10^5,k\leq 26,t\leq 100$ **solution** 显然前面摆一堆 `a` 更优，所以希望后面那一坨尽量的短 假设 $s(i)$ 表示 $i$ 个字符组成的后面那一坨 显然 $s(i)$ 变成 $s(i+1)$ 的过程中需要把所有的字母往后平移一格 那么 $s(i+1)$ 前面至少要有两个 `a`，因为 $s(i)$ 的开头肯定是一个 `a` 同理，因为对于每一个前缀和后缀，我们都保证的是 `a` 比 `b` 恰好多1，所以在每一个 `b` 后面我们需要给他接上一个 `a` [code](http://xsy.gdgzez.com.cn/JudgeOnline/showsource.php?id=290211) ## xsy NOI2021冬令营模拟测试赛（二十五） A duliu **description** 给定一个数列，$m$ 次询问，每次询问 $l,r,x$ 表示，这个数列中区间 $[l,r]$ 的所有连续子区间 $[a,b]$ 满足 $2\times (b-a+1)\times (sum_b-sum_{a-1})\geq x$ 中，$\max_{a\leq i\leq b}A_i$ 的最小值是多少 $n\leq 3\times 10^5,A_i\leq 10^7$ **solution** 最开始想到的是一个整体二分+线段树维护max（区间和$\times$区间长度）的 $\mathcal O(n\log ^2n)$ 的做法 后来看 sol 可以一个log 显然 $[a,b]$ 只能是 $[l,pl],[pr,r]$ 或者 $[a,b]$ 满足 $A_{a-1},A_{b+1}>\max_{a\leq i\leq b}A_i$ 对于前一类，我们可以直接二分找到 对于后一类，这样的区间只会有 $\mathcal O(n)$ 个 我们可以通过按照大小加入，利用并查集合并的方法找到这些区间 然后我们把询问离线一下，把询问区间和第二类区间都从大到小排序 按照顺序加到一棵线段树里面 对于询问 $[l,r]$，实际上我们只需要查找 $a\in[l,pr]$ 的部分 问什么这样是对的呢，显然在 $pr$ 右边的肯定都没有意义 如果在 $[l,pr]$ 中有一个区间的右端点在 $r$ 的右边，那么这个区间一定不优于 $[pr,r]$，所以这样依然是对的 $\mathcal O(n\log n)$ [code](http://xsy.gdgzez.com.cn/JudgeOnline/showsource.php?id=290213) ## P3641 [APIO2016]最大差分 **background** 一月最后一题 函数交互第一题 **description** [link](https://www.luogu.com.cn/problem/P3641) **solution** 对于前三十分我们可以先知道 $a_1,a_n$ 然后 $MinMax(a_1+1,a_n-1,a_2.a_{n-1})$ 就知道 $a_2,a_{n-1}$ 了，最多调用 $\dfrac{n+1}{2}$ 次 对于后七十分 我们肯定还是要先求出 $a_1$ 和 $a_n$ 那么显然我们的答案是大于等于 $\dfrac{a_n-a_1}{n-1}$ 的，所以我们对于序列按照这个长度分块。 显然同一块里面的数我们是不需要考虑的，只需要考虑每一块的最小值和前面一个有数的块的最大值的差即可 这样的话，我们需要最多做 $n+1$ 次查询，查询到了 $n+n-2$ 个数，所以可以在 $3n-1$ 的次数内得到答案，符合条件 [code](https://www.luogu.com.cn/record/45875342)