题目描述

给你一个数列 $a_{1..n}$，进行 $m$ 次询问，每次询问给出一个区间 $[l, r]$ 及参数 $w$，询问 $\max_{i = l}^{r-w+1}\{\min_{j=i}^{i+w-1}\{a_j\}\}$。

数列长度和询问次数 $10^5$。

题目描述

给你一棵有根树，一开始每个点都有不同的颜色。有三种操作：

1. 给定 $x$，将 $x$ 到根的路径修改为一种当前树上没有出现的颜色。
2. 给定 $x$ 和 $y$，询问 $x$ 到 $y$ 的路径上不同颜色的数量。
3. 给定 $x$，令一个点的权值为它到根路径上不同颜色的数量，求子树 $x$ 中的最大权值。

点数和操作数 $10^5$。

题目描述

给你一张边带权的无向连通图，多次修改，每次修改一条边的边权，每次修改完后求最小生成树的边权之和。

点数 $2\cdot 10^4$, 边数和修改数 $5\cdot 10^4$，时限 3s。

题意简述

给你一张边带权且边从 $1$ 到 $m$ 编号的无向图 $G$，称一张图 $H$ 是“好的”，当且仅当存在一个 $H$ 的生成子图 $F$ 使得 $F$ 中每个点的度数都是奇数。现在，你需要回答 $m$ 个问题，第 $i$ 个问题是：求最小的 $x$，使得仅保留 $G$ 中编号不超过 $i$ 且边权不超过 $x$ 的边时，得到的生成子图是“好的”，或者指出不存在这样的 $x$。

$2\le n\le 10^5$, $1\le m\le 3\cdot 10^5$, TL 4s。