自动搬运

查看原文

来自洛谷，原作者为

	fish_love_cat 「要毁灭世界，根本不需要邪恶。起初，那些都是不会被任何人怪罪的小小愿望。而那样的愿望却如此轻易地，和末日相连在一起。」

搬运于2025-08-24 22:59:24，当前版本为作者最后更新于2024-06-15 22:11:07，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

好玩的构造题！

---

设 $c,z,s,b,x,h$ 分别为序列 $a$ 中某个子串 $t$ 中第一大的值，第二大的值，长度，贡献，第二小的值和第一小的值。

依题意得：

当 $c+z\le q$ 时，则有 $b=\frac{s^2-s}{2}$。

当 $x+h>q$ 时，则有 $b=0$。

---

根据上面的条件可知：

当存在一个正整数 $i$ 满足 $p=\frac{i^2-i}{2}$ 时，则有关于序列 $a$ 的 $c,z$ 满足 $c+z\le q$。（情况一）

否则，必存在一个正整数 $i$ 满足 $\frac{i^2-i}{2}<p<\frac{i^2+i}{2}$。（情况二）

---

考虑对两种情况分别进行构造。

---

情况一：

我们可以构造出一个长度为 $i$ 且满足关于该序列的 $c,z$ 有 $c+z\le q$ 的序列 $a_1$，然后再构造出一个长度为 $n-i$ 且满足关于该序列的 $x,h$ 有 $x+h> q$ 的序列 $a_2$。将这两个数列的元素放在一起，就构造出了合法的序列 $a$。

因为题目保证 $p\le \frac{n(n-1)}{2}$，所以一定可以构造出这样的合法序列 $a$。

---

情况二：

因为有 $p=\frac{i^2-i}{2}+(p-\frac{i^2-i}{2})$，所以我们不妨将贡献拆成 $\frac{i^2-i}{2}$ 和 $p-\frac{i^2-i}{2}$ 两部分来分别构造。

显然 $\frac{i^2-i}{2}$ 的那部分可以用类似情况一的方式构造出一个长为 $i$ 的序列 $a_1$。

注意到，$i> p-\frac{i^2-i}{2}$。

设 $k,l$ 均为正整数。

所以我们可以构造一个数字为 $q-l$，并将 $a_1$ 在保持它仍合法的情况下，将里面的数字设为若干个 $l$ 和若干个 $l+k$。注意要求合法，即不违反情况一中对 $a_1$ 的定义。

再设 $j$ 是当前 $a_1$ 中元素 $l$ 的个数。

显然的，修改后的贡献会在之前的基础上加上 $j$。

我们通过构造使 $j=p-\frac{i^2-i}{2}$ 即可。

剩下的，用类似情况一的方式构造一个长为 $n-i-1$ 的 $a_2$。

将这两个数列的元素和 $q-l$ 放在一起，就构造出了合法的序列 $a$。

---

关于情况二中 $i\ge p-\frac{i^2-i}{2}$ 的证明：

$$\frac{i^2+i}{2}> p$$ $$i+\frac{i^2-i}{2}> p$$ $$i> p-\frac{i^2-i}{2}$$

证毕。

---

然后就可以开始愉快的构造了。

其实下面已经不重要了，看着上面相信大家都能构造出来对叭。

但还是介绍一下我的方法：

首先，$O(n)$ 跑一遍暴力求 $i$。

令 $k=l=1$，对于情况一中 $a_1$ 的构造，令元素全部为 $1$ 即可，而 $a_2$ 的构造，官解是全部 $10^7$，我是全 $q$，都能过的。

代码看不看其实无所谓吧。

懒得放了，注意求 $i$ 的时候跑不到 $n+1$ 可能会死在 #1。

做完了。提交记录。

---

后话：

不知道怎么搞的，老是想到一些情况二的构造无法胜任的情况。不过按理来说能让情况二构造出锅的数据都会被情况一构造掉吧，所以大抵是 hack 不掉的。

至少现在看解法没什么问题。

至少我自以为的证伪 hack 居然都满足情况一，很神奇，欢迎 hack（