发现在题目专区里发的题解不会在讨论总版里出现后我非常生气，于是有了本贴（。 原文：https://www.acgo.cn/problemset/97291/67514?tab=explanation。 吐槽一下，怎么必须要 AC 了才能发题解，害的我还得先登审核号把自己赛时代码拷过来。 我们需要充分发挥人类智慧，仔细观察样例 1 后可以发现当我们对每一行删去最小值后每一行都是一样的。 不妨大胆猜测，如果每一行不一样那么一定不行，如果每一行一样则一定为最优方案。 很显然，当每一行相同时，只需要一直做竖向操作即可，操作唯一。 然后就有以下代码： 竟然 WA 了！ 也是非常神奇。 然后我们动用观察力可以发现有如下 hack。 正常应该输出 1，直接竖着做一遍即可。 于是可以找到漏洞，不一样要先把每一行的最小值减去，先减每一列也行。于是我们把行列交换再做一次，两次取最小值。 有如下代码： 然后就过了（？） 声明： > 本题解为恶搞做法，不保证思路正确，欢迎大家尝试 hack 本题解，或证明本题解正确性。 彩蛋： > 比赛结束三分钟后 cjdst 在 Q 群问 T3 正解是啥，ta 给出了自己一个解方程的做法（显然太吃操作了，对于我这种不会有理数加减法的蒟蒻来讲），我也分享了我的恶搞做法，于是有了本题解。（甚至 cjdst 说以后自己也要乱搞打巅峰赛。

最近，我们团的队员老是用手动判断钻空子权力大的直接抄答案！！怎么办，在线加好友求救。

有帅哥美女能公布一下今年NOIP的四道题解吗(要AC的)

0 < ai < 102000 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ???

T1；糖果店（CANDY） 题干 P14635 [NOIP2025] 糖果店 题目描述 小 X 开了一家糖果店，售卖 nnn 种糖果，每种糖果均有无限颗。对于不同种类的糖果，小 X 采用了不同的促销策略。具体地，对于第 iii (1≤i≤n1 \le i \le n1≤i≤n) 种糖果，购买第一颗的价格为 xix_ixi 元，第二颗为 yiy_iyi 元，第三颗又变回 xix_ixi 元，第四颗则为 yiy_iyi 元，以此类推。 小 R 带了 mmm 元钱买糖果。小 R 不关心糖果的种类，只想得到数量尽可能多的糖果。你需要帮助小 R 求出，mmm 元钱能购买的糖果数量的最大值。 输入格式 输入的第一行包含两个正整数 n,mn, mn,m，代表糖果的种类数和小 R 的钱数。 输入的第 i+1i+1i+1 (1≤i≤n1 \le i \le n1≤i≤n) 行包含两个正整数 xi,yix_i, y_ixi ,yi ，分别表示购买第 iii 种糖果时第奇数颗的价格和第偶数颗的价格。 输出格式 输出一行一个非负整数，表示 mmm 元钱能购买的糖果数量的最大值。 输入输出样例 #1 输入 #1 输出 #1 输入输出样例 #2 输入 #2 输出 #2 说明/提示 【样例 1 解释】 小 R 可以购买 4 颗第一种糖果，共花费 4+1+4+1=104 + 1 + 4 + 1 = 104+1+4+1=10 元。 【样例 2 解释】 小 R 可以购买 1 颗第一种糖果、1 颗第二种糖果与 6 颗第三种糖果，共花费 1+2+12=151 + 2 + 12 = 151+2+12=15 元。 【样例 3】 见选手目录下的 candy/candy3.in 与 candy/candy3.ans。 该样例满足测试点 666 的约束条件。 【样例 4】 见选手目录下的 candy/candy4.in 与 candy/candy4.ans。 该样例满足测试点 8,98,98,9 的约束条件。 【样例 5】 见选手目录下的 candy/candy5.in 与 candy/candy5.ans。 该样例满足测试点 11,1211,1211,12 的约束条件。 【样例 6】 见选手目录下的 candy/candy6.in 与 candy/candy6.ans。 该样例满足测试点 131313 的约束条件。 【样例 7】 见选手目录下的 candy/candy7.in 与 candy/candy7.ans。 该样例满足测试点 17,1817,1817,18 的约束条件。 【数据范围】 对于所有测试数据，均有： * 1≤n≤1051 \le n \le 10^51≤n≤105； * 1≤m≤10181 \le m \le 10^{18}1≤m≤1018； * 对于所有 1≤i≤n1 \le i \le n1≤i≤n，均有 1≤xi,yi≤1091 \le x_i, y_i \le 10^91≤xi ,yi ≤109。 ::cute-table{tuack} 测试点编号 n≤n \len≤ m≤m \lem≤ 特殊性质 111 111 101010 无 2,32,32,3 222 202020 ^ 4,54,54,5 101010 ^ ^ 666 10210^2102 10210^2102 A 777 ^ ^ B 8,98,98,9 ^ ^ 无 101010 10310^3103 10410^4104 A 11,1211,1211,12 ^ ^ B 131313 ^ ^ 无 141414 10510^5105 10910^9109 A 15,1615,1615,16 ^ ^ B 17,1817,1817,18 ^ ^ 无 19,2019,2019,20 ^ 101810^{18}1018 ^ 特殊性质 A：对于所有 1≤i≤n1 \le i \le n1≤i≤n，均有 xi=yix_i = y_ixi =yi 。 特殊性质 B：对于所有 1≤i≤n1 \le i \le n1≤i≤n，均有 xi≥yix_i \ge y_ixi ≥yi 。 入口 洛谷入口：P14635 [NOIP2025] 糖果店 ACGO入口：A92615 [NOIP2025] 糖果店 解析 记所有糖果中 xi+yix_i + y_ixi +yi  最小的糖果为 ttt，最终选择的结果可看作选取 2k2k2k 个糖果 ttt 与其余若干糖果各一个，需满足 2kt+xp1+xp2+…+xpc≤m2kt + x_{p_1} + x_{p_2} + \ldots + x_{p_c} \leq m2kt+xp1 +xp2 +…+xpc ≤m。由于仅买一个的糖果应选取 xxx 最小的一部分，因此先将所有糖果按 xxx 的大小排序，枚举购买 111 个的糖果数量，剩余钱用于成对购买糖果 ttt（两个两个买），即可得到最大购买数量。 标程 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T2：清仓甩卖（SALE） 题干 P14636 [NOIP2025] 清仓甩卖 题目背景 额外提供了 0.5 秒的时限。 题目描述 小 X 的糖果促销策略很成功，现在糖果店只剩下了 nnn 颗糖果，其中第 iii (1≤i≤n1 \le i \le n1≤i≤n) 颗糖果的原价为 aia_iai 元。小 X 计划将它们全部重新定价，清仓甩卖。具体地，小 X 会将每颗糖果的清仓价格分别定为 111 元或 222 元。设第 iii (1≤i≤n1 \le i \le n1≤i≤n) 颗糖果的清仓价格为 wi∈{1,2}w_i \in \{1,2\}wi ∈{1,2} 元，则它的性价比被定义为原价与清仓价格的比值，即 aiwi\frac{a_i}{w_i}wi ai 。 小 R 又带了 mmm 元钱买糖果。这一次，小 R 希望他购买到的糖果的原价总和最大，于是他采用了以下购买策略：将所有糖果按照性价比从大到小排序，然后依次考虑每一颗糖果。具体地，若小 R 在考虑第 iii (1≤i≤n1 \le i \le n1≤i≤n) 颗糖果时剩余的钱至少为 wiw_iwi 元，则他会购买这颗糖果；否则他会跳过这颗糖果，继续考虑下一颗。特别地，若存在两颗糖果的性价比相同，则小 R 会先考虑原价较高的糖果；若存在两颗糖果的性价比与原价均相同，则小 R 会先考虑编号较小的糖果。 例如，若小 X 的糖果商店剩余 333 颗糖果，原价分别为 a1=1a_1=1a1 =1，a2=3a_2=3a2 =3，a3=5a_3=5a3 =5，而清仓价格分别为 w1=w2=1w_1=w_2=1w1 =w2 =1，w3=2w_3=2w3 =2，则性价比分别为 1,3,521, 3, \frac{5}{2}1,3,25 。因此小 R 会先考虑第 222 颗糖果，然后考虑第 333 颗糖果，最后考虑第 111 颗糖果。 小 R 想知道，在小 X 的所有 2n2^n2n 种定价方案中，有多少种定价方案使得他按照上述购买策略能购买到的糖果的原价总和最大。你需要帮助小 R 求出满足要求的定价方案的数量。由于答案可能较大，你只需要求出答案对 998,244,353998,244,353998,244,353 取模后的结果。 输入格式 本题包含多组测试数据。 输入的第一行包含两个非负整数 c,tc, tc,t，分别表示测试点编号与测试数据组数。c=0c=0c=0 表示该测试点为样例。 接下来依次输入每组测试数据，对于每组测试数据： * 第一行包含两个正整数 n,mn, mn,m，分别表示糖果的数量与小 R 的钱数； * 第二行包含 nnn 个正整数 a1,a2,…,ana_1, a_2, \ldots, a_na1 ,a2 ,…,an ，分别表示每颗糖果的原价。 输出格式 对于每组测试数据，输出一行一个非负整数，表示使得小 R 购买到的糖果的原价总和达到最大值的定价方案数对 998,244,353998,244,353998,244,353 取模后的结果。 输入输出样例 #1 输入 #1 输出 #1 说明/提示 【样例 1 解释】 该样例即为【题目描述】中的例子。共有以下 666 种定价方案使得小 R 购买到的糖果原价总和最大，分别为： * w1=w2=w3=1w_1 = w_2 = w_3 = 1w1 =w2 =w3 =1，小 R 购买到的糖果原价总和为 888； * w1=w3=1w_1 = w_3 = 1w1 =w3 =1，w2=2w_2 = 2w2 =2，小 R 购买到的糖果原价总和为 666； * w1=1w_1 = 1w1 =1，w2=w3=2w_2 = w_3 = 2w2 =w3 =2，小 R 购买到的糖果原价总和为 555； * w2=w3=1w_2 = w_3 = 1w2 =w3 =1，w1=2w_1 = 2w1 =2，小 R 购买到的糖果原价总和为 888； * w3=1w_3 = 1w3 =1，w1=w2=2w_1 = w_2 = 2w1 =w2 =2，小 R 购买到的糖果原价总和为 555； * w1=w2=w3=2w_1 = w_2 = w_3 = 2w1 =w2 =w3 =2，小 R 购买到的糖果原价总和为 555。 注意：若 w1=w2=1w_1 = w_2 = 1w1 =w2 =1，w3=2w_3 = 2w3 =2，则小 R 会依次购买第 222 颗和第 111 颗糖果，原价总和为 444，但小 R 可以只购买第 333 颗糖果，原价总和为 555。因此该定价方案无法使小 R 购买到的糖果的原价总和达到最大值。 【样例 2】 见选手目录下的 sale/sale2.in 与 sale/sale2.ans。 该样例满足测试点 1∼31 \sim 31∼3 的约束条件。 【样例 3】 见选手目录下的 sale/sale3.in 与 sale/sale3.ans。 该样例满足测试点 4,54,54,5 的约束条件。 【样例 4】 见选手目录下的 sale/sale4.in 与 sale/sale4.ans。 该样例满足测试点 7∼97 \sim 97∼9 的约束条件。 【样例 5】 见选手目录下的 sale/sale5.in 与 sale/sale5.ans。 该样例满足测试点 10∼1210 \sim 1210∼12 的约束条件。 【样例 6】 见选手目录下的 sale/sale6.in 与 sale/sale6.ans。 该样例满足测试点 131313 的约束条件。 【样例 7】 见选手目录下的 sale/sale7.in 与 sale/sale7.ans。 该样例满足测试点 14,1514,1514,15 的约束条件。 【样例 8】 见选手目录下的 sale/sale8.in 与 sale/sale8.ans。 该样例满足测试点 171717 的约束条件。 【样例 9】 见选手目录下的 sale/sale9.in 与 sale/sale9.ans。 该样例满足测试点 19,2019,2019,20 的约束条件。 【样例 10】 见选手目录下的 sale/sale10.in 与 sale/sale10.ans。 该样例满足测试点 21∼2321 \sim 2321∼23 的约束条件。 【样例 11】 见选手目录下的 sale/sale11.in 与 sale/sale11.ans。 该样例满足测试点 24,2524,2524,25 的约束条件。 【数据范围】 设 NNN 为单个测试点内所有测试数据的 nnn 的和。对于所有测试数据，均有： * 1≤t≤5×1041 \le t \le 5 \times 10^41≤t≤5×104； * 1≤n≤5,0001 \le n \le 5,0001≤n≤5,000，N≤5×104N \le 5 \times 10^4N≤5×104，1≤m≤2n−11 \le m \le 2n - 11≤m≤2n−1； * 对于所有 1≤i≤n1 \le i \le n1≤i≤n，均有 1≤ai≤1091 \le a_i \le 10^91≤ai ≤109。 ::cute-table{tuack} 测试点编号 n≤n \len≤ N≤N \leN≤ mmm 特殊性质 1∼31\sim 31∼3 555 5,0005{,}0005,000 ≤2n−1\le 2n - 1≤2n−1 无 4,54,54,5 101010 ^ ^ ^ 666 404040 ^ ^ ^ 7∼97\sim 97∼9 300300300 ^ =2=2=2 ^ 10∼1210\sim 1210∼12 ^ ^ ≤2n−1\le 2n - 1≤2n−1 B 131313 ^ ^ ^ 无 14,1514,1514,15 10310^3103 10410^4104 =2=2=2 ^ 161616 ^ ^ =2n−1=2n - 1=2n−1 ^ 171717 ^ ^ =2n−2=2n - 2=2n−2 ^ 181818 ^ ^ ≤2n−1\le 2n - 1≤2n−1 A 19,2019,2019,20 ^ ^ ^ B 21∼2321\sim 2321∼23 ^ ^ ^ 无 24,2524,2524,25 5,0005{,}0005,000 5×1045 \times 10^45×104 ^ ^ 特殊性质 A：a1=a2=⋯=ana_1 = a_2 = \cdots = a_na1 =a2 =⋯=an 。 特殊性质 B：对于所有 1≤i≤n1 \le i \le n1≤i≤n，均有 ai>5×108a_i > 5 \times 10^8ai >5×108。 入口 洛谷：P14636 [NOIP2025] 清仓甩卖 ACGO：A92616.[NOIP2025] 清仓甩卖 解析 1. 不优方案的条件 当存在三种糖果 X,Y,ZX,Y,ZX,Y,Z 满足 * wX=wZ=1w_X = w_Z = 1wX =wZ =1，wY=2w_Y = 2wY =2 * aX+aZ<aYa_X + a_Z < a_YaX +aZ <aY  且 aZ<12aY<aX<aYa_Z < \frac{1}{2}a_Y < a_X < a_YaZ <21 aY <aX <aY 贪心策略会因 XXX 性价比较高而错选 X,ZX,ZX,Z，忽略总收益更高的 YYY（ZZZ 可不存在）。核心问题是考虑 YYY 时仅剩 111 元，无法购买。 2. 方案数计算枚举糖果 * X,YX,YX,Y，将其他糖果分类： 1. 原价大于 aYa_YaY  的糖果(c1(c_1(c1  个）：必被选中，消耗 111 或 222 元 2.原价在 aX,aYa_X,a_YaX ,aY  之间的糖果(c2(c_2(c2  个)：出清价为 111 元时被选中，否则忽略 * 不合法方案数为 Cc1+c2m−c1−2C_{c_1+c_2}^{m-c_1-2}Cc1 +c2 m−c1 −2 （保证考虑 YYY 时仅剩 $1￥ 元）考 * 虑 ZZZ 的取值方案（含不存在情况），总方案数为 2c3×Cc1+c2m−c1−22^{c_3} \times C_{c_1+c_2}^{m-c_1-2}2c3 ×Cc1 +c2 m−c1 −2 ，其中 c3c_3c3  为原价不低于 ZZZ 的糖果数 标程 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T3：树的价值（TREE） 题干 P14637 [NOIP2025] 树的价值 题目描述 给定一棵 nnn 个结点的有根树，其中结点 1 为根，结点 iii (2≤i≤n2 \le i \le n2≤i≤n) 的父亲结点为结点 pip_ipi 。 对于 1≤i≤n1 \le i \le n1≤i≤n，定义结点 iii 的深度 did_idi 为结点 1 到结点 iii 的简单路径的边数，也就是说，d1=0d_1 = 0d1 =0，di=dpi+1d_i = d_{p_i} + 1di =dpi +1 (2≤i≤n2 \le i \le n2≤i≤n)。定义有根树的高度 hhh 为所有结点的深度的最大值，即 h=max⁡i=1ndih = \max_{i=1}^{n} d_ih=maxi=1n di 。 给定高度的上界 mmm。在本题中，给定的有根树的高度不超过 mmm。 你需要给每个结点设置一个非负整数作为它的权值。对于 1≤i≤n1 \le i \le n1≤i≤n，若结点 iii 的权值为 aia_iai ，令 SiS_iSi 表示结点 iii 的子树中结点权值构成的集合。对于每一种权值设置方案，定义树的价值为 ∑i=1nmex(Si)\sum_{i=1}^{n} \mathrm{mex}(S_i)∑i=1n mex(Si )，其中 mex(S)\mathrm{mex}(S)mex(S) 表示不在集合 SSS 中的最小非负整数。例如，在下图中，若设置 a1=3a_1 = 3a1 =3，a2=2a_2 = 2a2 =2，a3=a4=0a_3 = a_4 = 0a3 =a4 =0，a5=1a_5 = 1a5 =1，则 S1={0,1,2,3}S_1 = \{0,1,2,3\}S1 ={0,1,2,3}，S2={0,1,2}S_2 = \{0,1,2\}S2 ={0,1,2}，S3={0}S_3 = \{0\}S3 ={0}，S4={0}S_4 = \{0\}S4 ={0}，S5={1}S_5 = \{1\}S5 ={1}，树的价值为 4+3+1+1+0=94 + 3 + 1 + 1 + 0 = 94+3+1+1+0=9。 你需要求出，在所有权值设置方案中，树的价值的最大值。 输入格式 本题包含多组测试数据。 输入的第一行包含一个正整数 ttt，表示测试数据组数。 接下来依次输入每组测试数据，对于每组测试数据： * 第一行包含两个正整数 n,mn, mn,m，分别表示结点数量与高度的上界。 * 第二行包含 n−1n - 1n−1 个正整数 p2,p3,…,pnp_2, p_3, \ldots, p_np2 ,p3 ,…,pn ，分别表示每个结点的父亲结点。 输出格式 对于每组测试数据，输出一行一个非负整数，表示树的价值的最大值。 输入输出样例 #1 输入 #1 输出 #1 说明/提示 【样例 1 解释】 该样例共包含两组测试数据。 对于第一组测试数据，可以设置 a1=3a_1 = 3a1 =3，a2=2a_2 = 2a2 =2，a3=a4=0a_3 = a_4 = 0a3 =a4 =0，a5=1a_5 = 1a5 =1，则树的价值为 4+3+1+1+0=94 + 3 + 1 + 1 + 0 = 94+3+1+1+0=9。 对于第二组测试数据，可以设置 a1=4a_1 = 4a1 =4，a2=3a_2 = 3a2 =3，a4=2a_4 = 2a4 =2，a3=a6=1a_3 = a_6 = 1a3 =a6 =1，a5=a7=0a_5 = a_7 = 0a5 =a7 =0，则树的价值为 5+4+2+0+1+0+1=135 + 4 + 2 + 0 + 1 + 0 + 1 = 135+4+2+0+1+0+1=13。 【样例 2】 见选手目录下的 tree/tree2.in 与 tree/tree2.ans。 该样例满足测试点 3,43,43,4 的约束条件。 【样例 3】 见选手目录下的 tree/tree3.in 与 tree/tree3.ans。 该样例满足测试点 7,87,87,8 的约束条件。 【样例 4】 见选手目录下的 tree/tree4.in 与 tree/tree4.ans。 该样例满足测试点 13,1413,1413,14 的约束条件。 【样例 5】 见选手目录下的 tree/tree5.in 与 tree/tree5.ans。 该样例满足测试点 18,1918,1918,19 的约束条件。 【数据范围】 对于所有测试数据，均有： * 1≤t≤51 \le t \le 51≤t≤5； * 2≤n≤8,0002 \le n \le 8,0002≤n≤8,000，1≤m≤min⁡(n−1,800)1 \le m \le \min(n - 1, 800)1≤m≤min(n−1,800)； * 对于所有 2≤i≤n2 \le i \le n2≤i≤n，均有 1≤pi≤i−11 \le p_i \le i - 11≤pi ≤i−1； * 给定的有根树的高度不超过 mmm。 ::cute-table{tuack} 测试点编号 n≤n \len≤ m≤m \lem≤ 1,21,21,2 777 n−1n-1n−1 3,43,43,4 131313 ^ 5,65,65,6 181818 ^ 7,87,87,8 404040 ^ 9,109,109,10 120120120 ^ 11,1211,1211,12 360360360 ^ 13,1413,1413,14 4,0004{,}0004,000 222 15∼1715\sim 1715∼17 ^ 101010 18,1918,1918,19 ^ 505050 20∼2520\sim 2520∼25 8,0008{,}0008,000 800800800 入口 ACGO入口：A92617.[NOIP2025] 树的价值 洛谷入口：P14637 [NOIP2025] 树的价值 解析 1. 核心定义 * 白点：不清空未分配权值节点，继承子树的 mex 值 * 黑点：清空未分配权值节点，增大 mex 值 * 状态定义： f[i][j][k]f[i][j][k]f[i][j][k]：白点i是树链第j个点，贡献为kkk的最大价值 g[i][j]g[i][j]g[i][j]：黑点i是树链第j个点的最大贡献2. 优化思路 * 性质：j≤kj \leq kj≤k（否则选黑点更优），k−jk-jk−j 不超过子树最深深度用长链剖分优化 DP 转移，时间复杂度O(nm)O(nm)O(nm)后缀加操作通过数据结构优化，最终时间复杂度O(nmlog⁡n)O(nm\log n)O(nmlogn) 标程 76PTS ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 序列询问（QUERY） 题干 P14638 [NOIP2025] 序列询问 题目背景 额外提供了 1 秒的时限。 题目描述 给定一个长度为 nnn 的整数序列 a1,a2,…,ana_1, a_2, \ldots, a_na1 ,a2 ,…,an 。 有 qqq 次询问，其中第 jjj (1≤j≤q1 \le j \le q1≤j≤q) 次询问将会给出 Lj,RjL_j, R_jLj ,Rj (1≤Lj≤Rj≤n1 \le L_j \le R_j \le n1≤Lj ≤Rj ≤n)。定义区间 [l,r][l, r][l,r] (1≤l≤r≤n1 \le l \le r \le n1≤l≤r≤n) 是极好的，当且仅当区间 [l,r][l, r][l,r] 的长度在 [Lj,Rj][L_j, R_j][Lj ,Rj ] 内，即 Lj≤r−l+1≤RjL_j \le r - l + 1 \le R_jLj ≤r−l+1≤Rj 。定义区间 [l,r][l, r][l,r] (1≤l≤r≤n1 \le l \le r \le n1≤l≤r≤n) 的权值为 ∑i=lrai\sum_{i=l}^{r} a_i∑i=lr ai 。对于所有 i=1,2,…,ni = 1, 2, \ldots, ni=1,2,…,n，求出所有包含 iii 的极好区间的最大权值，即 max⁡1≤l≤i≤r≤n{∑i=lrai∣Lj≤r−l+1≤Rj}\max_{1 \le l \le i \le r \le n} \{ \sum_{i=l}^{r} a_i \mid L_j \le r - l + 1 \le R_j \}max1≤l≤i≤r≤n {∑i=lr ai ∣Lj ≤r−l+1≤Rj }。 输入格式 输入的第一行包含一个正整数 nnn，表示序列长度。 输入的第二行包含 nnn 个整数 a1,a2,…,ana_1, a_2, \ldots, a_na1 ,a2 ,…,an 。 输入的第三行包含一个正整数 qqq，表示询问次数。 输入的第 j+3j + 3j+3 (1≤j≤q1 \le j \le q1≤j≤q) 行包含两个正整数 Lj,RjL_j, R_jLj ,Rj ，表示第 jjj 次询问。 输出格式 对于每次询问，设包含 iii (1≤i≤n1 \le i \le n1≤i≤n) 的极好区间的最大权值为 kik_iki ，输出一行一个非负整数，表示 ⨁i=1n((i×ki) mod 264)\bigoplus_{i=1}^{n} \left( (i \times k_i) \bmod 2^{64} \right)⨁i=1n ((i×ki )mod264)，其中 ⊕\oplus⊕ 表示二进制按位异或。注意：对于任意整数 xxx，存在唯一的非负整数 x′x'x′ 满足 x′≡x(mod264)x' \equiv x \pmod{2^{64}}x′≡x(mod264) 且 0≤x′≤264−10 \le x' \le 2^{64} - 10≤x′≤264−1，则记 x mod 264=x′x \bmod 2^{64} = x'xmod264=x′。 输入输出样例 #1 输入 #1 输出 #1 说明/提示 【样例 1 解释】 对于第 111 次询问： * 包含 111 的极好区间为 [1,1][1,1][1,1] 和 [1,2][1,2][1,2]，权值分别为 2,62,62,6； * 包含 222 的极好区间为 [1,2][1,2][1,2]，[2,2][2,2][2,2] 和 [2,3][2,3][2,3]，权值分别为 6,4,−16,4,-16,4,−1； * 包含 333 的极好区间为 [2,3][2,3][2,3]，[3,3][3,3][3,3] 和 [3,4][3,4][3,4]，权值分别为 −1,−5,−4-1,-5,-4−1,−5,−4； * 包含 444 的极好区间为 [3,4][3,4][3,4] 和 [4,4][4,4][4,4]，权值分别为 −4,1-4,1−4,1。 因此 k1=6k_1 = 6k1 =6，k2=6k_2 = 6k2 =6，k3=−1k_3 = -1k3 =−1，k4=1k_4 = 1k4 =1。 对于第 2 次询问，k1=2k_1 = 2k1 =2，k2=2k_2 = 2k2 =2，k3=2k_3 = 2k3 =2，k4=2k_4 = 2k4 =2。 对于第 3 次询问，k1=6k_1 = 6k1 =6，k2=6k_2 = 6k2 =6，k3=2k_3 = 2k3 =2，k4=2k_4 = 2k4 =2。 【样例 2】 见选手目录下的 query/query2.in 与 query/query2.ans。 该样例满足测试点 2,32,32,3 的约束条件。 【样例 3】 见选手目录下的 query/query3.in 与 query/query3.ans。 该样例满足测试点 444 的约束条件。 【样例 4】 见选手目录下的 query/query4.in 与 query/query4.ans。 该样例满足测试点 6,76,76,7 的约束条件。 【样例 5】 见选手目录下的 query/query5.in 与 query/query5.ans。 该样例满足测试点 8∼108 \sim 108∼10 的约束条件。 【样例 6】 见选手目录下的 query/query6.in 与 query/query6.ans。 该样例满足测试点 11,1211,1211,12 的约束条件。 【样例 7】 见选手目录下的 query/query7.in 与 query/query7.ans。 该样例满足测试点 131313 的约束条件。 【样例 8】 见选手目录下的 query/query8.in 与 query/query8.ans。 该样例满足测试点 16∼2016 \sim 2016∼20 的约束条件。 【数据范围】 对于所有测试数据，均有： * 1≤n≤5×1041 \le n \le 5 \times 10^41≤n≤5×104，1≤q≤1,0241 \le q \le 1,0241≤q≤1,024； * 对于所有 1≤i≤n1 \le i \le n1≤i≤n，均有 ∣ai∣≤105|a_i| \le 10^5∣ai ∣≤105； * 对于所有 1≤j≤q1 \le j \le q1≤j≤q，均有 1≤Lj≤Rj≤n1 \le L_j \le R_j \le n1≤Lj ≤Rj ≤n。 ::cute-table{tuack} 测试点编号 n≤n \len≤ q≤q \leq≤ 特殊性质 111 10310^3103 111 无 2,32,32,3 3,0003{,}0003,000 505050 ^ 444 10410^4104 128128128 ^ 555 3×1043 \times 10^43×104 512512512 ^ 6,76,76,7 5×1045 \times 10^45×104 1,0241{,}0241,024 A 8∼108 \sim 108∼10 ^ 512512512 B 11,1211,1211,12 ^ ^ C 131313 ^ 1,0241{,}0241,024 D 14,1514,1514,15 ^ ^ E 16∼2016 \sim 2016∼20 ^ ^ 无 特殊性质 A：对于所有 1≤j≤q1 \le j \le q1≤j≤q，均有 Lj=RjL_j = R_jLj =Rj 。 特殊性质 B：对于所有 1≤j≤q1 \le j \le q1≤j≤q，均有 Rj≤32R_j \le 32Rj ≤32。 特殊性质 C：对于所有 1≤j≤q1 \le j \le q1≤j≤q，均有 Lj≤16L_j \le 16Lj ≤16 且 Rj≥n−1000R_j \ge n - 1000Rj ≥n−1000。 特殊性质 D：对于所有 1≤j≤q1 \le j \le q1≤j≤q，均有 Lj>n/2L_j > n/2Lj >n/2。 特殊性质 E：对于所有 1≤j≤q1 \le j \le q1≤j≤q，均有 Lj>n/4L_j > n/4Lj >n/4。 入口 洛谷入口P14638 [NOIP2025] 序列询问 ACGO入口A92618.[NOIP2025] 序列询问 做法一：分块预处理 1.预处理区间 [ql,qr]=[2k,2k+1−1][q_l, q_r] = [2^k, 2^{k+1}-1][ql ,qr ]=[2k,2k+1−1] 的答案 2.询问时将区间拆分为整块（预处理结果）和散块（满足 2ql>qr）3.2q_l > q_r） 3.2ql >qr ）3.散块通过 O(1)O(1)O(1) RMQ 求解，总时间复杂度 O(nlog⁡n+nq)O(n \log n + nq)O(nlogn+nq) 做法二：二维区间拆分 * 将可行区间拆分为两类三角形： 包含 [l,r][l,r][l,r] 且长度 ≤ LLL被 [l,r][l,r][l,r] 包含且长度 ≥ LLL枚举边界区间，结合前缀 min / 后缀 max 和单调栈维护覆盖关系，总时间复杂度 O(n)O(n)O(n) per query ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 感悟 真的，难度是越来越大了，2026年难度不堪设想

题不在多，计算则烦 码不在长，递归/推则难 斯是OI，唯吾摆烂 WA满江红，AC红绿灯 谈笑有巨佬，往来无蒟蒻 可以调代码，翻讨论。 贪心过样例，骗分TLE。暴力还CE。 小码**云：何AK之有

自创的？

怎么回事,怎么老PE

防透视 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 展示： 请打开浅色模式\color{white}{请打开浅色模式}请打开浅色模式 请打开深色模式\color{#121624}{请打开深色模式}请打开深色模式 神马你竟然看见了!\color{transparent}{神马你竟然看见了!}神马你竟然看见了! ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 方法：

返回目录 一个小游戏，放心，很安全的，没有WINDOWS库 3.3版本来啦！！！欢迎各路大佬给出建议。 这次更新了趣味玩法和选择先后手。 广告：一个小团队聊天室入口 一个小团队入口

招人帖子【欢乐赛团队】（内涵大佬）

家人们，作者在此😆✨@空港急行列车就是题目中の黄鼠狼本尊😜👍😎

for(i=0;i<=k;i++){ #额*****************哪错了？ }

咨询/举报/公开赛/变更权限 ，请在此举报。 关于题目... 题目需按照一下格式 题目 哪里出错 ... @Earth.

首先我要声明这个帖子是举报贴，如果有违反可删除 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 【实名控诉】关于用户【我是冤枉的㥇。餐】的违规行为曝光 ⚠️ 举报对象 用户名：我是冤枉的㥇.餐，官方不知道真相 用户 ID：1763421 主页链接：点击查看 首先他已经有很多犯罪前科了，在以前的时候毁了我的团队，现在又毁了陶源和蠢泰的团队，我问了他，他回答说是因为陶源和他有仇，不知道是我的团队，搞笑的是他说一个人能有多个团队（当时没有转让功能）。还有那个蠢泰、陶源，我们他们同一个班级的，真是辈辈出人才，蠢泰被禁言老实了又来了一个㥇.餐 证据： 团队成员变更 2025-03-10 用户【༺ཌༀ餐·戔ༀད༻】将用户【和平地铁单人四排的神】移出【BACKROOMS】团队 团队成员变更 2025-03-10 用户【༺ཌༀ餐·戔ༀད༻】将用户【‭‭‭‭‭‭‭‭‭‭‭‭‭‭‭‭】移出【BACKROOMS】团队 团队成员变更 2025-03-10 用户【༺ཌༀ餐·戔ༀད༻】将用户【༺ཌༀ杨婉宁ༀད༻】移出【BACKROOMS】团队 团队成员变更 2025-03-10 用户【༺ཌༀ餐·戔ༀད༻】将用户【赖昱宸】移出【BACKROOMS】团队 团队成员变更 2025-03-10 用户【༺ཌༀ餐·戔ༀད༻】将用户【159****9543】移出【BACKROOMS】团队 我虽然当时是小团队，但被他这样一毁更垃圾了 现在这个**被禁言了7天就开始发SJ了，详情可看他的主页，不知道是不是XBY的祖孙三代 目前已经被禁言7天了，那我不多说什么了，如果以后再有类似的话，我一定S了他 在这我也贴一下脸，如果这些事是假的，我全家S觉，SHI痕遍野 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 欢迎加入我们终极领域 我被毁的团队终焉之地 @༺ཌༀ膏·罪ༀད༻@༺ཌༀ陶·源ༀད༻@复仇者_༺ཌༀ皴·泰ༀད༻所联合创作 支持一下终极领域的活动25届ACGO双色球（有几率获得管理员）

刷题团队于2025年11月30日成立特殊班级:疯班，无论你是打游戏输了，刷题一直失败，还是单纯想发疯，都可以加入哦 刷题团队特殊班：疯班 另外，如果您有需要，可以申请加入 刷题团队 刷题团队附属团 刷题团队自习室 刷题团队特殊班：疯班 急需招人，申请必过 快来加入刷题团队吧

对不起，在之前的日子中，我（刷题团队）进行过过度广告刷屏行为，我（刷题团队）承认宣传过于急躁，没有遵守纪律，对此，我代表刷题团队正式向所有看过广告的用户道歉！！！ 后面，我将会在公平的前提下合理宣传团队，已1位起始值，每次+1并邀请对应id用户！如果不想被邀请，可以私信团长，脚本将会跳过您的id 此外，宣传团队的工作不会再由我进行，我会邀请我们班幸运的同学进行宣传，同时规范方式，将链接等整合到一篇铁子里，发送帖子链接，不会再帖子下多次发送，只进行单次发送。只进行单次发送。此外，团长将会减少acgo的使用，在df社区继续未完成的铁子，如果单纯想看作者的可以准备let us go了，还有，我总结了一下几点，望周知 1.我会静下心来，进行深入地学习与反思，从根本上提升自己在公共事务中的认知水平、社会责任感和判断力。 2.未来在任何公开场合、作品创作及宣发中，我将以最高标准要求自己:更加审慎言行，加强内容审核机制，对潜在敏感话题保持高度警惕，确保始终传递积极、正向的价值。 3.真诚接受并聆听大家持续的批评与监督。你们的每一条意见，都是我成长路上最宝贵的镜鉴和前行的动力。 再次向大家表达我最深的歉意。这次教训非常深刻，我会铭记于心，并将这份愧疚转化为前进的动力。未来，我将始终坚守编程初心，用实际行动来证明我的改变和决心，努力成为一个更专业、更负责、更值得大家信赖和支持的团长焦梓睿，在未来用更好的作品和更积极的表现来回报大家。 感谢大家花费宝贵的时间阅读这封信。我代表刷题团队再次向大家说一声:对不起!

各位大佬、狐朋狗友们，大家好。由于大号被禁言了，所以用小号发这篇帖子。 写下这篇帖子的时候，心中开心死了。经过长时间的慎重考虑，我决定正式退出这个陪伴了我2年的地方。 做出这个决定并不难，但也是我目前阶段被逼无奈的选择。 最近，我需要将更多的精力投入到紧张的学业中，时间和精力实在无法兼顾。为了不影响和大家交流的质量，也为了不辜负这份陪伴，我选择暂时告别。 生活总是充满了新的变数，我即将进入一个新的生活阶段，需要一些时间和空间去适应和调整。网络上的世界虽然精彩，但我需要暂时回归现实，去处理一些更重要的事情。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 【回顾与感谢】 回想当初，我是因为一群志同道合的朋友而来到这里。在这里，我收获了虚假的友谊 ，认识了像@AAA冰块批发AI哥@MOLLY@༺ཌༀ膏·罪ༀད༻这样一群可爱的人，我们一起在赛时交流竞赛答案，这些回忆都非常不珍贵。 宝贵的知识 ：从各位大佬和前辈的分享中，我学到了很多关于使用AI的技巧的东西，让我受益匪浅。 纯粹的快乐 ：那些关键时刻AI赐予我的帮助，是我平淡生活中的一抹亮色。 感谢ACGO提供了这样一个交流的平台，感谢ID36482一直以来的辛勤维护和管理，更要感谢每一位关注我、和我互动过的朋友。你们的每一次点赞、评论和私信，都曾给我带来过温暖和鼓励。 【最后的祝福】 天下没有不散的筵席，但我们的缘分并不会因此结束。 虽然我即将离开，但我会默默关注着这里的发展，为ACGO的越来越好而感到高兴。也祝愿在这里的每一位大佬： 学业蒸蒸日上，前程似锦！ 学业蒸蒸日上，前程似锦！ 学业蒸蒸日上，前程似锦！ 生活美满，身体健康，万事顺遂！ 生活美满，身体健康，万事顺遂！ 生活美满，身体健康，万事顺遂！ 在ACGO玩得开心，交到更多好朋友！ 在ACGO玩得开心，交到更多好朋友！ 在ACGO玩得开心，交到更多好朋友！ 我的账号将在这个号的个性签名变为“NULL”停止更新，并逐渐淡出大家的视线。如果大家想找我，可以等到2030年（这里不小心打错了，闹了个笑话）我回归，退站期间可以尽情骚扰我呦！（不过别造谣！）（不过别造谣！）（不过别造谣！） 再次感谢大家这一路的陪伴。聚散终有时，江湖再相逢。回归后我一定会以脸皮为桨，AI为帆，继续在AI和人类的分界线处徘徊！ 退站期间别把我封号了啊！我团队交给130****4826保管。 祝好！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 𝓬𝓾𝓷𝓽𝓪𝓲 2025年11月6日 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 小彩蛋（摊几张牌）：\color{yellow}{小彩蛋（摊几张牌）：}小彩蛋（摊几张牌）： ID：4978429（我小号）\color{yellow}{ID：4978429（我小号）}ID：4978429（我小号） ID：4978433（我小小号）\color{yellow}{ID：4978433（我小小号）}ID：4978433（我小小号） ID：5197667（我小小小小号）\color{yellow}{ID：5197667（我小小小小号）}ID：5197667（我小小小小号） 笑点分析：现在𝓐𝓘𝓮𝓻的排位分还没他小号高\color{yellow}{笑点分析：现在𝓐𝓘𝓮𝓻的排位分还没他小号高}笑点分析：现在𝓐𝓘𝓮𝓻的排位分还没他小号高 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 最后希望𝓐𝓘𝓮𝓻个人主页的青铜和禁言标志能时刻提醒那些AIER，不要在错误的路上越走越远！