这个题考场上想到 slope trick 去了。但是事实上不需要那么麻烦。 一个朴素的想法是，设 $f_{i,j}$ 为考虑了前 $i$ 个数，第 $i$ 个数改为了 $j$ 的最小代价，有转移式： $$ f_{i,j}=\min_{k\in[j-d,j+d]}f_{i-1,k}+|a_i-j| $$ 要优化这个 DP…

这个题的转化非常神。 首先发现给的这个 $p$ 是没有用的，因为赢了输了多少局都是确定的。 然后，如果我们把初始状态看成一个坐标系上的 $(0,0)$，终点看成 $(n,m)$，相当于是我们每次赢就往右走一步，输就往上走一步。每次赢了就 $x\gets x+1$，输了就 $x\gets \max(x-1,0)$。我们现…

在讨论《申请撤下本题的一些莫队题解》回复：

@[Register_int](luogu://user/406941) ?

在讨论《申请撤下本题的一些莫队题解》回复：

@[run_away](luogu://user/964089) 因为太多了

如题，题解区全是莫队做法，但是正如 [这篇文章](https://codeforces.com/blog/entry/104443) 介绍的一样，其实有不带根号的分治做法，所以申请撤下一些莫队题解并重新打开题解提交

在讨论《求原题》回复：

这不是我们玩具装箱吗。。

将数列按 $c$ 分块，则一个查询 $[l,r]$ 的贡献由以下几部分组成： 1. $[l,r]$ 之间的整块的最大子段和。 2. $l$ 到第一个整块之间的最大子段和。 3. 最后一个整块到 $r$ 的最大子段和。 4. 整块与整块之间的跨边界的最大子段和。 5. $l$ 与第一个整块之间跨边界的最大子段和。 6.…

发现如果我们枚举 $l_2\le r_1$，则合法的 $l_1,r_2$ 会形成一段前后缀。其中，如果我们设 $last_i$ 表示 $a_i$ 上一次出现的位置，$next_i$ 为 $a_i$ 下一次出现的位置，则所有合法的 $l_1$ 必须要满足 $l_1\ge \max_{i=l_2}^{r_1} last_i…

在讨论《求助 CSP-J2/S2》回复：

@[rsy_](luogu://user/550775)这已经是你这个月第二次发批话贴了

首先将 $\phi(x)$ 拆成 $\phi(x)= x \prod_{p | x} \frac {p-1}{p}$，发现我们要求的式子其实可以转化为 $\sum_{S} (\prod a_i)\prod_{p|\prod a_i} \frac {p-1}{p}$。 发现其实我们只关心哪些质数 $p$ 在最终的乘积里出…

考虑这么一个问题，如何通过函数 $f(x)$ 关于分布 $q$ 的期望 $E_q[f(x)]$，估计函数 $f(x)$ 关于概率分布 $p$ 的期望 $E_p [f(x)]$。 一个方法是使用重要性采样： $$ \begin{aligned} E_p[f(x)] &= \int f(x)p(x) dx\\ &=\int…

在讨论《因大量脚本导致的提交评测现状说明》回复：

支持

在讨论《hack》回复：

@[0000pnc](/user/603277) 哦，私密马赛，这个每次建边是独立的，可以提到分治外边做，但是我已经退役了，如果有好心人帮我改改的话就改改吧，不能的话我找个时间自己改了

在讨论《向中山纪念中学与洛谷致歉》回复：

@[kkksc03](/user/1) 请求置顶

在讨论《向中山纪念中学与洛谷致歉》回复：

选择自己写不合法的洛谷rmj是我的选择，报校外培训班也是我自己的选择，很抱歉对学校带来困扰，希望学校与教练原谅

先给被我这个事影响的同学、学校致歉。发这个帖是来说明一下我这个破事，并且反思一下自己所犯下的错误。 一、有关动机 在组比赛的时候会遇到需要使用多个oj的题目的情况，所以写了一个洛谷的rmj。在今年5月以前，这个网站一直是我个人在使用，没有通过网站盈利。 在4月以后，有一个oi机构的培训老师找到我，我让他使用我的网站进行…

当你打反转左右儿子的标记时，不要这样： ```cpp void reverse(int p) { if (!p) return; tr[p].rev = true; // wrong swap(tr[p].son[0], tr[p].son[1]); } ``` 而是: ```cpp void reverse(int…

货物只能往编号更大的节点运。。。

在讨论《小细节》回复：

@[KingPowers](/user/530180) 永畜塔菲你咋这么牛

在讨论《pbds 快还是 set 快？》回复：

@[DengDuck](/user/501947) 听说pbds写的很史

在讨论《20分性感代码在线求调》回复：

@[rsy_](/user/550775) 你好性感

在讨论《如果你整体二分15分》回复：

@[Svemit](/user/503792) 喝喝你的果汁

在讨论《RAND_MAX=32767时有什么均匀生成大随机数的方法吗》回复：

@[zjh114514](/user/773944) rand() * RAND_MAX + rand()

在讨论《一个关于并查集的疑问》回复：

@[An_Idiot](/user/708963) 这还需要推导吗，这不是人为定义的吗

在讨论《萌新求助站外题》回复：

设 $f_{i,j,k}$ 表示考虑分成了 $i$ 份，第 $i$ 份为 $j$，$N$ 剩下 $k$ 的方案数，然后dp就行

在讨论《关于团队 GDHSOI 的惩罚公告》回复：

byd，在首页上看到发现和我们学校缩写咋这么像，再看看发现这两个出题人 ID 我不认识松了一口气，点进团队一看发现就是我们学校的 真难蹦

在讨论《稍微吐槽下这题的数据》回复：

没过就行）

在讨论《这题在卡什么？？》回复：

想被卡常的可以去写 ynoi，但是我来这题是想练习模板的