Trust Nobody
简单题，桶排序+前缀和以后直接找 \(n - sum_i = i\) 的 \(i\)
Lunatic Never Content
对于原序列的每一对不满足回文的位置，记录其差的绝对值取 \(\gcd\)。对于已经满足回文的，\(x\) 可以为 \(\infty\)，因此输出 \(0\)
Dreaming of Freedom
这道题主要考察线性筛。观察样例（如果观察不出可以多造几组数据）可以发现，如果 \(n\) 的最小质因数 \(\le m\)，则不能结束题述过程，输出 NO，否则输出 YES
Running Miles
求解三元组相关问题的一般套路
注意到对于满足题意的区间，其前三大值中的两个必然在区间的一头一尾，因此按顺序枚举中间的数（此处中间指位置上的中间而非大小上的中间），同时找到对当前数贡献最大的左端点，同理右端点也做相同处理，最终取最大值为答案
上述过程用到双指针的思想
Walk the Runway
这道题的难点在于想到它和图论有关，以及如何建图
首先在所有边之间都连上双向边，每读入一个城市的信息，就先按照 rating 排序，再去掉 \(\mathop{edge}\limits_{i = 1, j = i + 1}\limits^{i, j \le n} \left( r_i, r_j \right)\) 这些边（此处的 \(r_i\) 含义已经改变，指的是排序以后 \(r\) 数组原来的下标），可以证明最后得到的是一张有向无环图（此处证明留给读者思考），在此有向无环图上进行 DFS 得到最终答案
蒲公英（在线区间众数）
在线区间众数可谓分块思想的模板题，我调了整整 8 个小时才过，真是太菜了
看到值域 \(10^9\) 首先想到将序列 \(a\) 离散化，然后开始考虑问题
大体思路是把序列 \(a\) 分成 \(T\) 块，设每个询问 \(\left[ l, r \right]\) 包含的整块区间为 \(\left[ L, R \right]\)，有一个显然的性质，即区间 \(\left[ l, r \right]\) 的众数只可能是以下的数：
-
区间 \(\left[ L, R \right]\) 的众数
-
区间 \(\left[ l, L \right) \cup \left( R, r \right]\) 中出现过的数
因此我们得到以下解法：
-
以数组 \(sum_{i, j, k}\) 记录第 \(i\) 个块到第 \(j\) 个块中等于 \(k\) 的数有多少个，数组 \(mode_{i, j}\) 记录第 \(i\) 个块到第 \(j\) 个块的众数
-
扫描区间 \(\left[ l, L \right) \cup \left( R, r \right]\) 并将每个数出现过的次数直接累加到 \(sum_{L, R, k}\) 上
-
扫描一遍 \(sum_{L, R, k}\)，其众数就是要求的众数
-
再次扫描区间 \(\left[ l, L \right) \cup \left( R, r \right]\) 并给 \(sum_{L, R, k}\) 减去每个数出现过的次数，复原 \(sum\) 数组，供下次查询使用
该解法的时间复杂度为 \(O \left( NT^2 + \frac{MN}{T} \right)\)，当 \(NT^2 = \frac{MN}{T}\) 时取到最小值，解得 \(T = \sqrt[3]{N}\)，此时算法的时间复杂度和空间复杂度均为 \(O \left( N^{\frac{5}{3}} \right)\)，可以通过本题
标签：right,07,sum,个块,2023.06,众数,区间,日志,left From： https://www.cnblogs.com/xj22yangyichen/p/17464845.html