标签 整体二分 下的文章

「算法笔记」整体二分

「ZJOI 2013」K 大数查询

题目链接：BZOJ 3110

有 $n$ 个位置，$m$ 个操作。操作分为以下 $2$ 种：

• 1 a b c：表示在第 $a$ 个位置到第 $b$ 个位置，每个位置加入一个数 $c$。
• 2 a b c：表示询问从第 $a$ 个位置到第 $b$ 个位置，第 $c$ 大的数是多少。

数据范围：$1\le n,m\le 5\times 10^4$，操作 $1$ 中 $0\le \vert c \vert \le 2 ^ {63} - 1$。

「Luogu 2617」Dynamic Rankings

题目链接：Luogu 2617

给定一个含有 $n$ 个数的序列 $a_i$，接下来有 $m$ 个询问，询问分为以下 $2$ 种：

• Q i j k：询问区间 $[i,j]$ 排序后的第 $k$ 个数。
• C i t：将 $a_i$ 修改为 $t$。

数据范围：$1\le n, m \le 10 ^ 5$，$0 \le a_i \le 10^9$。