分块
「CF91E」Igloo Skyscraper-分块
· ✏️ 1032 words · ☕ 3 mins read

有 $n$ 个海象(编号为 $1$ 到 $n$ )参加比赛建造自己的摩天大楼 。在 $t=0$ 时,第 $i$ 个海象的摩天大楼的高度为 $a_i$ 。每一时刻,编号为 $i$ 的海象会完成 $b_i$ 层楼的建造。

在奥运会现场报道的记者向活动组织者提出了 $q$ 次询问。每次询问给出三个数字 $l_i$ ,$r_i$ ,$t_i$。活动组织者用数字 $x$ 回答每个查询,$x$ 满足:

  1. 数字 $x$ 位于从 $l_i$ 到 $r_i$ 的区间,即 $l_i \leq x \leq r_i$ 。

  2. 编号为 $x$ 的海象的摩天大楼在 $t_i$ 时刻拥有编号在 $[l_i,r_i]$ 中所有海象的摩天大楼中的最大高度。

对于每位记者的查询,输出符合上述标准的海象的编号 $x$ 。如果有多个可能的答案,请输出其中任何一个。


「CQOI2018」异或序列-莫队
· ✏️ 644 words · ☕ 2 mins read

已知一个长度为 $n$ 的整数数列 $a_1,a_2,…,a_n$ ,给定查询参数 $l$ 、 $r$ ,问在 $a_l,a _ {l+1},…,a_r$ ​区间内,有多少子序列满足异或和等于 $k$ 。也就是说,对于所有的 $x,y$ $(l \leq x \leq y \leq r)$ ,能够满足 $a_x \bigoplus a _ {x+1} \bigoplus … \bigoplus a_y = k$ 的 $x,y$ 有多少组。


「Luogu 2801」教主的魔法-分块
· ✏️ 459 words · ☕ 1 mins read

给定一个长度为 $N$ 的数列,每次一个操作或询问:

  • 把闭区间 $[L, R]$ 内的数全部加上一个整数 $W$
  • 问闭区间 $[L, R]$ 内有多少英雄身高大于等于 $C$

「Violet」蒲公英-分块
· ✏️ 1455 words · ☕ 3 mins read

给定一个数列 ${a_n}$ ,$m$ 次询问在 $[l,r]$ 区间内的最小众数。
强制在线。