给定一个长度为 的数列,和 次询问,求出每一次询问的区间内数字的最大值。
「LibreOJ #130」树状数组 1 :单点修改,区间查询
给定数列 ,你需要依次进行 q 个操作,操作有两类:
1 i x
:给定 i,x,将 ai 加上 x;2 l r
:给定 l,r,求 ∑i=lrai 的值(换言之,求 的值)。
「LibreOJ #109」并查集
维护一个 n 点的无向图,支持:
- 加入一条连接 u 和 v 的无向边
- 查询 u 和 v 的连通性
由于本题数据较大,因此输出的时候采用特殊的输出方式:用 0 或 1 代表每个询问的答案,将每个询问的答案依次从左到右排列,把得到的串视为一个二进制数,输出这个二进制数 mod 998244353 的值。
「NOIP2017」奶酪 - 并查集
现有一块大奶酪,它的高度为 h,它的长度和宽度我们可以认为是无限大的,奶酪中间有许多半径相同的球形空洞。我们可以在这块奶酪中建立空间坐标系, 在坐标系中,奶酪的下表面为 z=0,奶酪的上表面为 z=h。
现在, 奶酪的下表面有一只小老鼠 Jerry,它知道奶酪中所有空洞的球心所在的坐标。如果两个空洞相切或是相交,则 Jerry 可以从其中一个空洞跑到另一个空洞,特别 地,如果一个空洞与下表面相切或是相交,Jerry 则可以从奶酪下表面跑进空洞; 如果一个空洞与上表面相切或是相交,Jerry 则可以从空洞跑到奶酪上表面。
位于奶酪下表面的 Jerry 想知道,在不破坏奶酪的情况下,能否利用已有的空洞跑到奶酪的上表面去?