本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-11-27 17:46:48

山东提供的是 Windows + NOI Linux 虚拟机。使用 Linux 主要是为了测试编译、时间与内存限制。

传输文件

首先打开终端。按 Super 键（Windows 键）打开搜索框，搜索 terminal 并运行，打开的是一个深紫色背景窗口。

把文件复制到主文件夹，类比 Windows 中的用户目录。在终端中，可以用 ls 命令查看当前文件夹内有哪些文件，检查代码是否复制错了地方。

我在我的工作目录下输入 ls，会得到类似这样的信息：

蓝色的是目录、绿色的是可执行文件，白色的是普通文件。因为我的系统是日用的，所以和考场中有的文件夹不同。一般的，看到有 Documents、Desktop，或者 文档、桌面 等文件夹，就是主目录。

编译源代码

要编译 a.cpp ，可以输入命令：

g++ a.cpp -o a -Wall -Wextra -std=c++14 -O2 -g

其中，g++ 是必须的；a.cpp 是文件名，可以更改；-o a 是指定可执行文件名，Linux 下的可执行文件是不带后缀名的；-Wall -Wextra 是打开所有警告；-std=c++14 是指定标准；-O2 是打开优化，可以删掉；-g 是打开调试符号，不会使用调试器的可以忽略。

运行测试

编译后，可以用 ls 命令查看是否多出来了 a 文件，即指定的可执行文件名。随后，使用 .\/a 命令可以运行这个程序。

以 A + B 为例。我这里的源代码名为 c.cpp，我希望它编译成 c。使用如下命令并运行、输入，得到期望输出：

如果运行编译命令后出现额外信息，是编译错误或者警告，具体和 Dev C++ 下栏中显示的错误相同。比如我将 cin >> a >> b 误写作 cin >> a >> c，会得到：

我们看看 RE 会怎么样。如下图：

我们故意 RE。

Segmentation fault，或者 段错误，是内存访问越界，或者 STL 容器的使用出错。删掉 cout << q[0] << '\n'，看看除零：

会显示 Floating point exception，或 浮点错误 等。有的 STL 错误还会附带 STL 的错误信息，这点和 Windows 是大体一致的。

测试用时

测试程序用时，可以用 time 或者 \/bin\/time 命令，后者显示的更多，不会的可以只用前者。具体的，使用 time .\/a 命令运行并测速，其他的和不测速时一样。由于用键盘输入的时间计入总时，所以最好使用文件输入。

我们以测速 .\/c 为例。这里我用了文件输入输出。

这里我测试了两次，分别是同一份源代码，O2 与不开启 O2 的速度。测评时间是 user 行后面的。这里是 0.104s（O2）与 0.258s（无优化）。

测试内存

内存分为静态内存和动态的。静态的是直接开的全局数组、变量、还有代码本身的长度。动态的如 vector、栈等 STL 容器。

静态内存可以用 size 命令测试。

找到输出的 dec，也就是倒数第三个，6408903，就是静态内存占用，单位是字节。除以 1048576 得到以 MB 为单位的静态内存。

动态内存不好直接测试，但是可以通过限制总内存使用量来判断是否超过内存限制。具体命令是：ulimit -v X，其中 X 是内存限制，单位是 KB。或者，可以使用 ulimit -v $((X * 1024))，X 同样是内存限制，但单位是 MB。记不住可以计算器换算后用前者。

以下面程序为例。

笔算可知内存占用是大概是 380MB。我们把内存放到 256MB：

ulimit 命令前，执行是正常的。执行 ulimit 命令后，我们发现出现 RE。这是因为 MLE 了。

注意内存限制如果过小，会导致终端的正常任务无法执行。这时打开一个新终端即可。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-12-04 21:10:21

整理了一些关于 Splay 的资料，一个简洁美丽而高效的数据结构。

Splay 是最简洁的平衡树之一，支持维护区间信息。相比线段树，其可以动态地删点、加点，更加灵活；相比分块，其复杂度是均摊对数，更加高效。

在形态变化时，Splay 并不通过维护一系列性质来保证树高，而是通过伸展保证均摊复杂度。这让它少了常见平衡树的繁杂分讨，但常数也要大不少。

形态及操作

Splay 首先是一棵二叉搜索树，由许多节点组成。我们在每个节点维护父亲的左右儿子指针，以及键值。如有需要，还可以维护它子树内的信息，如它的子树大小。维护子树大小，可以实现快速查询第 k 大或者某数排名。

Splay 的核心操作是伸展（splay）。伸展某个节点 $x$，意味着将 $x$ 节点提升到根，同时更新所维护的子树信息。原来的根在伸展后成为某个普通内部节点。伸展操作的均摊复杂度是对数。

如果能够实现伸展操作，就可以方便地进行许多操作：

• 插入。插入与普通二叉树的插入相同，按照二叉树的遍历方法找到某个叶子节点，将新值插入到该叶子的儿子下。不同的是，在插入某个点后，为了保证复杂度正确，我们要将这个节点伸展到根。

• 删除。首先将这个节点伸展到根，然后将其与其儿子断开。这时原树分裂成两个子树，考虑合并它们。找到左子树的最大值，由二叉树的性质，这个数一定小于右子树的最小值。因此，我们将 $y$ 伸展到根。这时 $y$ 的右儿子一定空，于是将右子树拼到其右儿子上即可。

• 查找某个数。按照二叉树的查找方法，一直找到这个数，或者某个叶子。将最后找到的节点伸展到根。

• 查询排名。首先查找这个数，伸展到根。然后小于其的数数量就是现在根左子树的大小。如果待查询的值不存在，还要考虑根是否小于这个数。

• 查询第 $k$ 大。和二叉树相同。从根节点开始遍历。如果当前节点 $x$ 左子树的大小，也就是小于 $x$ 的数字数量，大于等于 $k$，要找的节点在左子树；如果等于 $k - 1$，那么就是当前节点 $x$；否则，在右子树，并且 $k$ 减去左子树加上当前点大小。

• 查询前驱。伸展到根，然后找左子树的最大值，也就是一直向右走。如果查询的值不存在，特判根是否小于待查值。

• 查询后继。与查询前驱同。

• 查询区间。设待查询区间为 $[l, r]$，我们将 $l - 1$ 旋到根，$r + 1$ 旋到根的右儿子，那么根的右儿子的左儿子，其上的信息就是 $[l, r]$ 的信息。

伸展

旋转

现在，我们只需要有效地实现伸展操作，就可完成所需的一切操作。

考虑怎么将某个节点高度提升一。我们称这个操作为旋转。

考虑怎么将 $2$ 提升到 $4$ 的位置。

那样，$4$ 该放到哪里？可以接到 $2$ 的右儿子上。$2$ 的右儿子放到哪里？放到 $4$ 的左儿子上，因为 $4$ 原来的左儿子是 $2$，现在已经空。其他子树不变。因此，变的只有 $2$ 和 $4$。

单旋与双旋

伸展操作能不能直接一直向上旋转呢？可以，但复杂度错误。

为了改善复杂度，我们需要引入双旋。

双旋是指，在伸展过程中，如果出现 $x$ 与 $x$ 的父亲同向，不能简单地旋转两次 $x$，而是要先旋转其父亲，再旋转 $x$。

我们如果想要将 $6$ 伸展到根，是不是需要双旋？答案是肯定的，因为 $4$ 和 $6$ 都是其父亲的右儿子，属于同向。如果是伸展 $3$，就不需要了。按照双旋的过程，我们先旋转 $4$，再旋转 $6$。也就是，先变成：

后旋转 $6$

光看上图，可能感觉双旋和单旋没有什么区别，但实际上在复杂度分析时，使用双旋可以保证某个性质，进而保证复杂度正确。

总之，我们已经知道了怎样以正确的复杂度将 $x$ 伸展到根。有关 Splay 的基本操作，就介绍完毕了。

附一份常数和美观程度都不错的实现。

复杂度

势能分析简介

我们发现，Splay 的复杂度来源于两部分，一部分是遍历，另一部分是伸展。让最终遍历到节点马上被伸展到根，就可以把复杂度都算在伸展里，进而只需证明伸展的复杂度。

我们采用势能分析。势能分析是指，引入某个势能函数 $\Phi(D)$，描述某时数据结构的状态。

设每次操作的代价是 $c_i$，每次操作后数据结构为 $D_i$。要证 $\sum c_i$ 有某上界。如果 $\Phi(D_n) - \Phi(D_0) = O(F(n))$，$\Phi(D_n) - \Phi (D_0) + \sum c_i = \sum (c_i + \phi(D_i) - \phi(D_{i - 1})) = O(G(n))$，显然 $\sum c_i = O(F(n) + G(n))$。

这样有什么好处？我们考虑，Splay 等数据结构复杂度分析的难处，在于我们只知道 $c_i$ 的一个很松的上界，而不好直接分析 $\sum c_i$。实际上，某个大的 $c_i$ 对数据结构的影响也是大的，会导致后续的操作 $c_i$ 更小；换句话说，不会出现所有 $c_i$ 都取到上界的情况。

引入势能函数后，每个很大的 $c_i$，可以用一个很小的 $\Phi(D_i) - \Phi(D_{i-1})$ 来平衡。因而可以更方便地放缩，并得到上界。

具体分析

我们设某个节点的势能函数为 $\phi(x) = \log \lvert x\rvert$（$\log$ 均以二为底；$\lvert x\rvert$ 表示 $x$ 的子树大小），$\Phi(D) = \sum \phi(x)$。显然的，$0\le \Phi(D) \lt n\log n$，并且 $\Phi(D_n) - \Phi(D_0) = O(n\log n)$。我们要证明每次伸展操作的均摊复杂度是对数。

伸展的分解

根据上面对 Splay 的介绍，我们可以将伸展分为三种具体操作。设 $x$ 为待伸展的节点，$y$ 为 $x$ 的父亲，$z$ 为 $y$ 的父亲。

• zig，即一次单旋，在 $y$ 为根时候发生。直接旋转 $x$，其深度减少一。发现这种旋转最多发生一次。

• zig-zig，即一次双旋，在 $y$ 和 $x$ 同向时发生。先旋转 $y$，后旋转 $x$。$x$ 深度减少二。

• zig-zag，即两次对 $x$ 的单选，在 $x$ 和 $y$ 不同向时发生。$x$ 深度减少二。

伸展的过程是数次 zig-zig 与 zig-zag 的组合，加上可能存在的一次 zig。

zig 的分析

旋转的复杂度为 $O(1)$，势能的变化量为

$\phi(x') + \phi(y') - \phi(x) - \phi(y) = \phi(y') - \phi(x) \le \phi(x') - \phi(x)$

因此摊还代价是 $O(1) + \phi (x') - \phi (x)$。

zig-zig 的分析

摊还代价是

$$ \begin{aligned} & c \ =& 1 + \phi(x') + \phi(y') + \phi(z') - \phi(x) - \phi(y) - \phi(z) \ =& 1 + \phi(y') + \phi(z') - \phi(x) - \phi(y) \ \end{aligned} $$

考虑怎么把 $1$ 去掉，因为如果引入 $1$，就会导致最终复杂度与旋转次数有关。

有：

$$ \begin{aligned} 2\phi(x') - \phi(x) - \phi(z') = \log (\dfrac{\lvert x'\rvert^2}{\lvert x\rvert\lvert z'\rvert}) \ge 1 \end{aligned} $$

这是因为 $\lvert x'\rvert \ge \lvert x\rvert+\lvert z'\rvert$。注意到不双旋时，此不等式不满足。这也是为什么双旋才能保证复杂度。

用这个不等式代换常数 $1$，得到

$$ \begin{aligned} & c \ \le& 2\phi(x') - \phi(x) - \phi(z') + \phi(y') + \phi(z') - \phi(x) - \phi(y) \ \le& 2\phi(x') - 2\phi(x) + \phi(y') - \phi(y) \ \le& 3\phi(x') - 3\phi(x) \ =& O(\phi(x') - \phi(x)) \end{aligned} $$

成功将常数消去，同时和前面的 $\phi(x') - \phi(x)$ 保持了一致。

zig-zag 的分析

类似的，我们有不等式：$2\phi(x') - \phi(y') - \phi(z') = \log (\dfrac{\lvert x'\rvert^2}{\lvert y'\rvert\lvert z'\rvert})\ge 1$

$$ \begin{aligned} & c \ &= 1 + \phi(x') + \phi(y') + \phi(z') - \phi(x) - \phi(y) - \phi(z) \ &= 1 + \phi(y') + \phi(z') - \phi(x) - \phi(y) \ &\le 2\phi(x') - \phi(y') - \phi(z') + \phi(y') + \phi(z') - \phi(x) - \phi(y) \ &\le 2\phi(x') - 2\phi(x) - \phi(y) \ &\le 2\phi(x') - 2\phi(x) \ &= O(\phi(x') - \phi(x)) \end{aligned} $$

综合

分析得到，zig 的摊还代价为 $O(1 + \phi(x') - \phi(x))$，而这种旋转最多一次；其他的两种旋转，摊还代价都是 $O(\phi(x') - \phi(x))$。这样，伸展的总代价就是 $O(\log \lvert x'\rvert - \log \lvert x\rvert + 1) = O(\log n)$。我们成功证明了伸展的复杂度是摊还对数，由此知道 Splay 的复杂度是正确的。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-12-14 21:39:25

设两个数为 $u, v$，且 $u = 2^{k_1}p_1, v = 2^{k2}p_2, p_1 \equiv p_2 \equiv 1 \mod 2$。

两种情况。不等和相等。对于不等的，钦定 $k_1 \lt k_2$，那么 $u + v = 2^{k_1} (p_1 + p_2 2^{k_2-k_1})$。由于 $p_1$ 奇，后面偶，所以贡献就是直接加起来。

然后就是相等。考虑到很恶心的是我们不知道这俩东西加起来会除多少个 $2$。暴力枚举 $k_1$ （$k_2$），再暴力枚举一个 $k$，表示 $u + v = 2^k p$ 其中 $p$ 奇。由于值域 $10^7$ 直接开桶维护数量以及和。但是恶心的是这么算会重，于是做一个唐的没边的容斥。属于是高射炮炮决蚊子，张成泽馋死了。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-09-15 07:30:16

题意

给定两个排列 $A$ 与 $P$，定义一次操作表示对于所有的 $1\le i \le n$，将 $A_i$ 替换为 $A_{P_i}$。要求进行任意非负整数次操作，求能得到的字典序最小的排列。

题解

我们由 $i$ 向 $P_i$ 连一条有向边，那么可以得到一张图。考虑到现在一次操作实际上就是每个下标步进一次。

这时我们发现，确定操作次数，最终的排列就确定；换句话说，确定某一个点移动多少步，整个排列就确定。由此，结合要让字典序最小，很自然地考虑到要让每个环上的第一个位置最小。

但是这样可能冲突。考虑有两个大小为 $3$ 和 $6$ 的环，假设第一个环上移动 $2$ 步最优，第二个环上移动 $1$ 步最优。这时无论怎么操作，两个环都无法同时最优。换句话说，这两个同余方程没有公共解。

由于我们还要保证字典序最小，那么显然是尽量满足前面的环，即最小位置在最前面的环。后面的环怎么办？考虑枚举每个环上移动的步数 $k$，使得 $k$ 和前面的同余方程不冲突，在此条件下满足字典序尽可能小（即最小位置放尽可能小的数）。

怎么判断某个 $k$ 是否满足前面的同余方程？考虑到这个同余方程的模数是前面所有环长的 $\text{lcm}$，是阶乘级别的，没法直接做（然而官方题解拿 Python 水了）。考虑到

$$ x\equiv a \pmod m \Leftrightarrow x\equiv a_i\pmod {m_i^{\lpha_i}} $$

其中 $m_i, \lpha_i$ 是 $m$ 的标准分解。

那么可以分解出环长的质因子。设 $f(p)$ 表示当前同余方程的解模 $p$ 的值。那么枚举操作次数 $k$ 的同时，要满足对环长的每一个质因子 $p$，$k \bmod p$ 都和 $f(p)$ 相同。满足这个条件的情况下，再让字典序尽可能小。

于是我们做完了。

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
const int N = 2e5 + 10;
int ps[N], minp[N], res[N], z[N], p[N], w[N], f[N], nr = 0;
bool vis[N];

void sieve (void)
{
	for (int i = 2; i < N; i++) {
		if (!minp[i]) ps[++nr] = i, minp[i] = i;
		for (int j = 1; ps[j] * i < N; j++) {
			minp[i * ps[j]] = ps[j];
			if (i % ps[j] == 0) break;
		}
	}
}

int main (void)
{
	int n;
	
	cin.tie (0)->sync_with_stdio (false);
	cin >> n;
	
	sieve ();
	memset (f, -1, sizeof f);
	
	for (int i = 1; i <= n; i++) cin >> w[i];
	for (int i = 1; i <= n; i++) cin >> z[i];
	for (int i = 1; i <= n; i++) if (!vis[i]) {
		int j = i;
		vector<int> q, p;
		
		while (!vis[j]) vis[j] = true, q.push_back (j), j = w[j];
		int l = q.size (), t = l;
		while (t > 1) {
			int u = minp[t], w = 1;
			while (t % u == 0) t \/= u, p.push_back (w *= u);
		}
		
		int k = -1;
		for (int i = 0; i < l; i++) {
			for (auto j : p) if (f[j] != -1 && i % j != f[j]) goto nxt;
			if (k == -1 || z[q[k]] > z[q[i]]) k = i;
			nxt:;
		}
		
		for (int i = 0; i < l; i++) res[q[i]] = z[q[(i + k) % l]];
		for (auto v : p) f[v] = k % v;
	}
	
	for (int i = 1; i <= n; i++) cout << res[i] << " \n"[i == n];
	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-09-20 20:48:19

看到题解区大神都写了 01 trie / 分治，根本看不懂，怎么办！

但是不要急！本题可以用根本没有思维含量的小常数基数排序 + 树状数组 $O(n\log n \log V)$ 狠狠草过去！

这就是基数排序带给我的自信

我们直接狠狠贪心，从高到低枚举每一位，然后计算异或上这一位或是不异或的逆序对数。如果变少了，就直接选上这一位。然后就做完了。

但是……

如果你就这样天真的写了一颗平衡树 / 离散化 + 树状数组交上去，就会发现出题人狠狠的草爆了你的码！

但是！

众所周知，存在一种叫做基数排序的东西……它可以用线性的时间把一堆整数排序。

我们这里的问题是，离散化的速度太慢，是个线性对数。考虑到可以用基数排序替代快速排序 + 二分进行离散化，于是我们就做完了。

附一个基数排序离散化模板，它是本题的大功臣！

void radix_sort (int n)
{
	int mx = 0;
	for (int i = 1; i <= n; i++) ww[i] = { w[i], i };
	for (int i = 1; i <= n; i++) q[w[i] & 0x7fff]++, mx = max (mx, w[i] & 0x7fff);
	for (int i = 1; i <= mx; i++) q[i] += q[i - 1];
	for (int i = n; i >= 1; i--) rr[q[w[i] & 0x7fff]--] = ww[i];
	for (int i = 0; i <= mx; i++) q[i] = 0;
	mx = nr = 0;
	for (int i = 1; i <= n; i++) q[rr[i].fi >> 15]++, mx = max (mx, rr[i].fi >> 15);
	for (int i = 1; i <= mx; i++) q[i] += q[i - 1];
	for (int i = n; i >= 1; i--) ww[q[rr[i].fi >> 15]--] = rr[i];
	for (int i = 0; i <= mx; i++) q[i] = 0;
	for (int i = 1; i <= n; i++) w[ww[i].se] = nr += i == 1 || ww[i].fi != ww[i - 1].fi;
}

以及 Submission

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-09-23 11:28:54

考虑到题目中的操作实际上就是给区间加上某个值，询问就是问某点和第一次大于等于 $k$ 的时间。

考虑到可以直接用可持久化线段树模拟这个过程。

可持久化线段树是可以用标记永久化的方法来实现某些区间操作的。具体来说，我们不将某个点上的标记下传，而是在询问时一路加上所有标记。

然后二分一个最早的树即可。实现不难。

#include <iostream>
using namespace std;
using i64 = long long;
const int N = 1e6 + 10;
struct node { i64 s; int l, r; } sg[20 * N];
int rt[N], id[N], cnt = 0;

void upd (int &u, int v, int x, int y, int l, int r, i64 k)
{
	int mid = (x + y) \/ 2;
	sg[u = ++cnt] = sg[v];
	if (l <= x && y <= r) return sg[u].s += k, void ();
	if (l <= mid) upd (sg[u].l, sg[v].l, x, mid, l, r, k);
	if (r > mid) upd (sg[u].r, sg[v].r, mid + 1, y, l, r, k);
}

i64 qry (int u, int x, int y, int p, i64 tag)
{
	int mid = (x + y) \/ 2;
	if (x == y) return sg[u].s + tag;
	if (p <= mid) return qry (sg[u].l, x, mid, p, tag + sg[u].s);
	else return qry (sg[u].r, mid + 1, y, p, tag + sg[u].s);
}

int main (void)
{
	int n, q, qid = 0;
	
	cin.tie (0)->sync_with_stdio (false);
	cin >> n >> q;
	for (int i = 1; i <= q; i++) {
		int opt;
		
		cin >> opt;
		if (opt == 1) {
			int x;
			i64 y, k;
			cin >> x >> y >> k;
			id[++qid] = i, upd (rt[qid], rt[qid - 1], 1, n, x, y, k);
		}
		else {
			int l = 1, r = qid, ans = -1, x;
			i64 y;
			
			cin >> x >> y;
			
			if (qry (rt[qid], 1, n, x, 0) < y) {
				cout << "0\n";
				continue;
			}
			
			while (l <= r) {
				int mid = (l + r) \/ 2;
				if (qry (rt[mid], 1, n, x, 0) >= y) r = (ans = mid) - 1;
				else l = mid + 1;
			}
			
			cout << id[ans] << '\n';
		}
	}
	return 0;

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-09-24 16:48:41

考虑证明按照 $s + w$ 贪心的正确性。

我们的贡献和位置是无关的，因此我们要证的仅仅是当 $s_i + w_i \lt s_j + w_j$ 时，若 $j$ 可以放在 $i$ 上头，那么 $i$ 就一定能放在 $j$ 上头。也就是说：任意一种方案，都可以是排序后顺序构造。

设 $p_i$ 表示当前方案中 $1$ 到 $i$ 所有箱子的重量和，那么我们已知 $p_{i-1} \le s_i, p_{j-1}\le s_j$，要证 $p_{i-1}\le s_j, p_{j-1} - w_i + w_j \le s_i$。

放缩代入得证。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-09-25 07:30:34

考虑到两个子树的并就是整个树，那么一个颜色在两个子树同时存在，当且仅当它在某一个子树中的出现次数不为它在整棵树里头的出现次数。

那么就做完了。因为这时候我们就可以钦定 $1$ 为根，然后对 $1$ 为根的每一个子树算一下它的答案。线段树维护这个是简单的。

然后可以线段树合并 / 树上启发式合并，做完了。

#include <iostream>
#include <vector>
using namespace std;
const int N = 1e5 + 10;
int rt[N], z[N], cntq[N], head[N], res[N], ecnt = 1, cnt = 0, n;
struct edge { int v, nxt; } e[N * 2];
struct node { int s, k, l, r; } sg[50 * N];
void add (int u, int v)
{
	e[++ecnt] = { v, head[u] }, head[u] = ecnt;
}

\/\/ 考虑到实际上就是不等于总出现次数的点的数量。可以直接线段树做。

void push_up (int i) { sg[i].s = sg[sg[i].l].s + sg[sg[i].r].s; }
void upd (int &u, int x, int y, int p)
{
	int mid = (x + y) \/ 2;
	if (!u) u = ++cnt;
	if (x == y) return sg[u].s = cntq[x] != ++sg[u].k, void ();
	if (p <= mid) upd (sg[u].l, x, mid, p);
	else upd (sg[u].r, mid + 1, y, p);
	push_up (u);
}

void merge (int &u, int v, int x, int y)
{
	int mid = (x + y) \/ 2;
	if (!u || !v) return u += v, void ();
	if (x == y) return sg[u].s = (sg[u].k += sg[v].k) != cntq[x], void ();
	merge (sg[u].l, sg[v].l, x, mid), merge (sg[u].r, sg[v].r, mid + 1, y);
	push_up (u);
}

void dfs (int u, int last)
{
	int nr = 0;
	for (int i = head[u]; i; i = e[i].nxt) {
		int v = e[i].v;
		if (v == last) nr = i \/ 2;
		else dfs (v, u), merge (rt[u], rt[v], 1, n);
	}
	upd (rt[u], 1, n, z[u]), res[nr] = sg[rt[u]].s;
}

int main (void)
{
	cin.tie (0)->sync_with_stdio (false);
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> z[i], cntq[z[i]]++;
	for (int i = 1, u, v; i < n; i++) cin >> u >> v, add (u, v), add (v, u);
	dfs (1, 0);
	for (int i = 1; i < n; i++) cout << res[i] << '\n';
	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-09-28 10:40:32

2024/9/26

要合理分配时间，合理为正解分配思考时间，冷静分析题目性质，不要不敢想正解。思路还是要打开。

2024/9/27

场上要冷静考虑状态以及转移，不要因为急就临时更改做法。简单题的分数要拿到手。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-10-07 10:38:22

Mighty Rock Tower

题意：一个石子堆，初始为空，每次操作可以放上一枚石子。设当前石子的数量是 $x$，那么这一轮有 $P_x$ 的概率一个石子掉落（石子掉落后 $x$ 仍不变）。求石子堆到 $n$ 个的期望步数。

设 $f_i$ 表示由 $i - 1$ 个石子堆到第 $i$ 个的期望步数。考虑从第 $i - 1$ 个石子堆上后发生了什么。

一种可能是全掉完了。概率是 $P_i^i$，代价是 $\sum\limits_{j=1}^i f_j$；

另一种可能是掉到某一个 $j$ 就不再掉，概率是 $P_i^{i-j} (1 - P_i)$，代价是 $\sum\limits_{k=j+1}^i f_j$。这里 $j\in [1, i]$。

还有根本没有掉的，但是根本没有贡献。

这个式子拆开 $1 - P_i$ 项化简，可以得到一个 $O(N)$ 转移。由于 $P_i$ 只有 $100$ 种，因此可以对每一种 $P_i$ 前缀优化。最终复杂度是 $O(n\max P)$。

Game on Sum (Hard Version)

先看 Subtask 1。设 $f(i, j)$ 表示 Bob 已经进行了 $i$ 轮，已经选择了 $j$ 轮加法，最后的值。

现在我们不知道 Alice 会选什么。但是设她会选 $t$，那么

$$ f(i, j) = \min (f(i - 1, j) - t, f(i - 1, j - 1) + t) $$

Bob 会让答案尽可能小，所以外面套一个 $\min$。这个式子显然是在取到均值的时候最大，因此 Alice 会取这两个转移路径的均值。于是我们得到

$$ f(i, j) = \dfrac {f(i - 1, j) + f(i - 1, j - 1)} 2 $$

边界是 $j = 0$ 和 $i = j$。$j = 0$ 时，Bob 全都选减法，因此 Alice 全给 $0$。$j = i$ 时，Bob 全选加法，因此 Alice 全给 $k$。

对于 Subtask 2，考虑每个位置对 $f(n, m)$ 的贡献。能贡献的位置只有 $f(i, i) = ki$，贡献路径是 $(i, j) \rightarrow (i + 1, j), (i + 1, j + 1)$，也就是竖着或者斜着走，方案数是 $n - i - 1\choose m - j$。贡献是多少？一开始的贡献是 $ki$，随着往下走一行，会除以一个二。一共走 $n - i$ 行，因此除以 $2^{n-i}$。

所以最后的答案是

$$ \sum\limits_{x=1}^{n-1} \dfrac{{n-x-1\choose m-j} kx}{2^{n-x}} $$

比较奇妙。