2020省选自闭记

<area/> <base/> <br/> <col/> <command/> <embed/> <hr/> <img/> <input/> <keygen/> <link/> <menuitem/> <meta/> <param/> <source/> <track/> <wbr/>

CF484E Sign on Fence

题目链接

题目描述

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

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

「SDOI2017」树点涂色

LOJ

题目描述

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

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

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

CF603E Pastoral Oddities(结论,LCT/分治+并查集)

题目链接

题意简述

给你一张边带权且边从 $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。

整体二分学习笔记

整体二分是一种离线算法,可以将一个修改同时作用于多个询问,从而减少不必要的开销,将二分答案从单次询问扩展到多次询问。

在一些题目中,相比与其它解法,整体二分可以避免复杂的数据结构,降低代码难度与空间复杂度。