本文章由 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}} $$

比较奇妙。

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

A

一秒能处理的是 $\min(x, y)$，用 $n$ 除，上取整即可。

B

$a_n$ 一定是正贡献，$a_{n-1}$ 一定是负贡献，其他的数可全分配成正贡献。因为只有正数，所以最优。

C

考虑设当前已确定的长度为 $L$，已确定的一个子串为 $Q$。每次尝试扩大 $Q$，往它的后面加上 $0$ 或者 $1$；如果答案都是 $0$，说明已经到达了结尾，需要改变扩展方向。

场上想到了大部分做法，但是没有考虑到第一次往后扩展不到的时候就可以直接往左扩展，因此询问次数超限。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-10-08 16:31:27

考虑到最后拼接成的值域区间是连续的。我们维护拼接出这段区间需要几个原序列中的区间。

考虑固定值域右端点 $r$，维护 $[l, r]$ 在原序列中的段数。考虑加入一个数，如果原序列中和他相邻的数还没有被加入，那么它是不会相邻的，序列段数全都加一。

如果和它相邻的某一个已经加入了，那么段数和原来一样。特别地，如果它的左右两边都已经被加入了，那么段数还要减去一。

我们每次数的就是以它为右端点，左边为 $1$ 或者 $2$ 的数的数量。考虑到每个数都是正的，那么 $1$ 或者 $2$ 一定是最小值或者次小值。于是我们做一个最小值 / 次小值计数就好了。线段树维护完了。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-10-08 20:13:36

考虑到如果是整个区间怎么做。设 $f_i$ 表示以 $i$ 为结尾的合法子序列数量。那么

$$ f_i = 1 + \sum\limits_{j\lt i, a_j\mid a_i} f_j $$

考虑可以扫描线。固定左端点，从后往前，考虑 $i$ 作为左端点对于后面的贡献。那么，所有是 $a_i$ 的的倍数的 $\rg a_i\mid a_j$，都可以使得 $f_j$ 加上 $1$。同时，可以间接转移，也就是使得 $a_i\mid a_j\mid a_k$ 的 $f_k$ 上头加上 $f_j$。

我们这么样就做完了。

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

考虑到每个点最多至多被两个集合包含。

如果只被一个集合包含，那么这个集合的状态就确定了；

如果被两个集合包含，那么我们就知道了这两个集合的关系。然后用带权并查集维护连通块大小，动态维护就好了。

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

全用质数是可以的。这样，我们考虑将所用的质数作为点，将所有点之间直接连边，表示这两个点可以相邻。任意一条边不能走一次以上。这就是一个欧拉回路问题。

我们考虑需要取多少个点。如果有 $m$ 个点，那么每个点都和 $m - 1$ 个点有边，同时有自环。那么是 $m(m-1) / 2 + m$ 条边，也就是用 $m$ 条边能构造出的最长的路径长度。

但是考虑当 $2\mid m$ 时是不存在欧拉回路的。也就是，我们没法把这些边全都用上。所以我们把用不掉的删掉。删除一条边，最好能减少两个奇点，所以至少删掉 $m/2 - 1$ 条边。这样能保证这张图存在一条欧拉路径。不妨把偶数到奇数的边删掉。