题意

给定长度为 的序列 ，支持 次操作：

1. 1 l r k ：将 每个数加
2. 2 l r k ：查询区间 中第 小值（第 小，非第 大）

思路 —— 带标记分块（下标分块）

预处理

• 取块长 （约 较优），共 块
• 每个块维护：
  • add[id]：整块加法懒标记
  • pos[i]：原数组下标（块内按原数组下标存储，便于散块修改）
  • sorted[id][ ]：块内元素在原数组中的下标，按 a[idx] + add[id] 升序排列

修改 —— 区间加

• 整块：直接 add[id] += k，不影响块内相对顺序
• 散块（不完整块）：
  • 对该块中被修改的位置，直接在原数组 a[i] += k
  • 然后暴力重构该块：按 a[pos[j]] + add[id] 对下标 pos[j] 重新排序

查询 —— 区间第 k 小

区间第 k 小无法直接维护，外层对值域二分答案 mid：

• 定义 check(mid) = 统计 中 < mid 的元素个数
  • 整块：在 sorted[id] 中 lower_bound，比较时用 a[idx] + add[id] < mid
  • 散块：暴力扫描原数组 a[i] + (所属块add) < mid
• 若 < mid 的个数 ，则答案在左半边；否则向右
• 二分终止时得到答案

值域范围：初始记录全局最小/最大值，修改时散块重构可更新最值，二分在此范围内进行可做剪枝。

复杂度

• 修改：
• 查询：
• 取 ，可通过

关键注意点

• 存下标排序，散块修改后只重构本块
• 二分值域用 long long，防止溢出
• 快读快写 + 块长适当调大有助于卡常
• 查询时整块要用 a[idx] + tag[id] 参与比较