简要题意

给定正整数 $n$，构造一个 $1$ 至 $n$ 的排列 $p_1,p_2,\dots,p_n$ 满足以下条件：

• 对于 $1 \le i \le n$，设 $c_i = \lceil \frac{p_1+p_2+\dots +p_i}{i} \rceil$，则在 $c_1,c_2,\dots,c_n$ 中至少有 $\lfloor \frac{n}{2} \rfloor$ 个质数。

$n \le 10^4$

解法

本题有很多（乱搞）解法，这里给出一个可以严格证明的做法。

考虑将 $c$ 的一个前缀都赋值成相同的质数。这可以通过取一个质数 $p$ 并将前缀排列成 $p, p-1, p+1, p-2, p+2, \dots$，这样长度为 $2\min(p, n-p+1)-1$ 的前缀的 $c$ 值都是 $p$。

根据 Bertrand's Postulate，对于任意整数 $x$，$[x,2x]$ 内至少存在一个质数。

取其中的任意一个质数，长度 $\left(2\lfloor \frac{n}{3}\rfloor-1 \right)$ 的前缀就都是质数了。

题目要求共有 $n$ 个结点，将其中 $k$ 个点染成黑色（本题解中为了方便描述，通称所有未染色的点为白点），求黑点两两距离及白点两两距离，使他们之和最大。

我们可以将距离转化为路径，然后再将路径拆分成边，就可以记录每条边被经过的次数，直接计算即可。

问题来了！：那么每条边会对答案贡献多少呢？

我们不妨设这条边的一侧共有 $w$ 个点，其中有 $t$ 个点被染成黑色了；

那么这一侧共有 $t$ 个黑点，（$w-t$）个白点；类似，另一侧有（$k-t$）个黑点，（$n-w-k+t$）个白点；

令 $sz$ 为这条边的边权，那么贡献就是 $val=sz*(t*(k-t)+(w-t)*(n-w-k+t))$;

解题的大致思路就是计算每条边对答案的贡献，最后利用状态转移方程求出最优解。

首先给出状态数组：$f[x][y]$;

$f[x][y]$ 表示给以 $x$ 为根结点的子树染上 $y$ 个点所得的对于整棵树的最大贡献；

方程如下：

$f[i][j]=max(f[i][j],f[i][j-t]+f[z][t]+val);$( $z$ 表示 $i$ 的子结点)

目标状态：$f[1][k]$;

PS:中间可能遇到非法情况，建议把 $f[x][y]$ 预处理成非法情况，方便跳过处理（代码最后有针对这点的样例，可自行调试）；

强烈建议参考代码理解！！！！！

Over.

(第一次写题解，不足之处请大家多多包涵》_《)

题意

$n$ 只猫娘，每只猫娘每天要么自己举行了排队，要么会追随自己最好的朋友去参加她要去的派对。

举办的派对有 $3$ 种类型，在每一天晚上都会有一只猫娘举办了某种类型的派对，这只猫娘会一直举行下去直到自己换类型，问每天晚上这三种类型的派对都几只猫娘参加。

思路

首先把猫 $i$ 与自己的朋友连一条有向边，那么整张图就是一个内向基环树。每当一只猫娘举行了派对，这个结点相当于把自己和父亲结点的连边断开了，我们就需要统计每个举办派对的结点子树大小。

如果我们直接对着每一天的修改一个一个做，那么要处理分裂的问题，也能做但是不是很好写，所以我们考虑倒着做。

具体来说，每一天把当前猫娘举办的派对的答案回溯到这只猫娘举办的上一个派对那里（因为这只猫娘从上一个派对到举行当前派对这段时间一直都没变），但是如果这是这只猫娘举办的第一个派对了，那么来她排队里的猫娘和她自己都会跟随她的父亲结点，相当于连上了一条边，可以直接用dsu做，假如当前父亲节点追随的结点举办了派对，那么我们需要把当前结点子树的大小统计进这个派对的类型中。

差点忘了，我们既然从后往前做了，那需要初始化每种类型在最后时刻的人数，可以直接把一直都没举行派对的猫娘直接和她们的父亲节点连起来，然后对于有派对的把对应类型类加上自己子树的大小，然后从后往前一步一步更新当前答案这题做完了。

有一个注意的点在于并查集合并方向要写对，不然只能得 $4$ pts（也可能是我写法问题）。

这题洛谷评蓝是不是太夸张了（

  通常的染色问题是NPC问题，但此题多了m−n<=5的限制，可以将图的大小缩小来解决。将问题拓展为：每条边有两个权值，分别表示两个点同色、不同色时的权值，而一张图染色后的权值就是每条边的权值之积。这样对应原问题时，每条边同色时的权值为0，异色时的权值为1。拓展后的问题可以进行“消点”操作，具体如下：

  • 度数为1的点可以直接删除，并在最终的答案上乘上k−1.

  • 对于度数为2的点，设这个点连向a和b，则可以删除这个点并在a和b之间连一条边，讨论这个点的颜色来决定这个点的权值。具体如下:

    – 如果a和b同色，则有一种情况是这个点与a与b均同色，k−1种情况是这个点与a与b均不同色；

    – 如果a和b不同色，则有k−2种情况是这个点与a与b均不同色，一种情况与a同色，一种情况与b同色。

根据以上规则即可算出新连的边的权值，使得新图与原图等价。

  新图中不会包含度数小于等于2的点，因此新图中的点数n与边数m满足3n≤2m，又因为m−n≤5，所以n≤10且m≤15.

  随后用状态压缩dp进行子集转移即可在O(nm3^n) 的时间内求出新图的权值。

这个题最开始叫根号序列的，因为这个题的三个算法分别是分块，根号分治和根号重构。

$cnt(k)$ 显然是好求的，只需要解决 $\sum [f_i=k]a_i$ 即可。

注意到 $a_i$ 是区间加的，但 $f_i$ 是单点改的，所以可以得到一个 $O(n\sqrt{n})$ 的分块做法。

维护 $s_{i,j},b_{i,j}$ 表示第 $i$ 块中数字 $j$ 的 $a_x$ 之和/个数，对于区间加，散块暴力修改 $a_i$，整块维护每个块的懒标记值 $t_i$，复杂度 $O(\sqrt{n})$。

对于区间询问 $k$，则第 $x$ 块对答案的贡献是 $s_{x,k}+b_{x,k}\times t_x$。复杂度 $O(\sqrt{n})$。

单点修改 $f$ 只需要暴力更改即可，复杂度 $O(1)$，这个过程只要维护好 $b,s$ 两个数组就行。

不难发现这个做法的空间复杂度为 $O(n\sqrt{n})$，但空间限制是 32 MB。考虑优化。

不难发现瓶颈在于 $b,s$，我们对每种数字都记录了 $\sqrt{n}$ 个信息，实际上，这种方法只适用于元素 $f_i$ 出现次数很多的情况，但若一种元素 $f_i$ 出现次数很少，直接暴力遍历也可以解决，考虑阈值分治。

先不考虑修改了 $f_i$ 的情况。若 $cnt(x)\ge \sqrt{n}$，则我们维护元素 $x$ 在 $\sqrt{n}$ 块的信息，反之用 vector 或链表维护元素 $x$ 在序列中的位置。

前者元素种类数不超过 $\sqrt{n}$，所以空间是 $O(n)$，后者显然是 $O(n)$。时间上，传统的分块做法单次查询 $O(\sqrt{n})$，而后者元素的出现次数不超过 $\sqrt{n}$，时间也是 $O(\sqrt{n})$。

考虑加入修改 $f_i$ 的操作，不难发现可能存在元素从 $cnt(x)$ 从 $\ge \sqrt{n}$ 变成 $< \sqrt{n}$。考虑定期重构，对操作分块，每 $\sqrt{n}$ 次操作就重新根号分治做初始化。

对于修改了 $f_i$ 的位置 $i$，在下一次重构前，我们不用分块也不用 vector 维护，而是把他们专门放到一个 vector 里，统计他们对每个询问的贡献，因为定期重构，这个 vector 内元素个数不超过 $\sqrt{n}$。

这一部分要注意把修改了 $f_i$ 的位置 $i$ 从原数据结构中删除，分块的直接删掉贡献，vector 可以用懒惰删除，最后总复杂度就是 $O(n\sqrt n)$。