标签: 分块

6 篇文章

LuoguP3793 由乃救爷爷
Description 题目链接:P3793 给定一个 $n$ 个数的序列,有 $m$ 个询问,每次询问区间最大值。 $1\leq n,m\leq 2\times 10^7$,保证数据随机。 Solution 考虑分块。 如果朴素分块肯定是不能过的 $O(N\sqrt{N})$,但是这题并没有修改操作,所以考虑先预处理出第 $l$ 个块到第 $r$…
LuoguP4168 [Violet]蒲公英
Description 题目链接:P4168 给定一个长度为 $n$ 的序列,$m$ 次询问,每次询问输出区间众数,如果出现次数相同,输出编号小的。 强制在线。 $1\leq n\leq 4\times 10^4,1\leq m \leq 5\times 10^4,1\leq a_i\leq 10^9$ Solution 看到区间众数,自然而然就想…
LuoguP5071 [Ynoi2015] 此时此刻的光辉
Description 题目链接:P5071 给定一个长为 $n$ 的序列,有 $m$ 次查询,每次查询一段区间的乘积的约数个数 $\bmod 19260817$ 的值。 $1\leq n,m \leq 10^5,1\leq a_i \leq 10^9$ Solution 乍看题目,不难想到一种很暴力的做法:先对每个数质因数分解,然后利用约数和定理…
LuoguP5356 [Ynoi2017] 由乃打扑克
Description 题目链接:P5356 一个长为 $n$ 的序列 $a$,需要支持 $m$ 次操作,操作有两种: 查询区间 $[l,r]$ 的第 $k$ 小值。区间 $[l,r]$ 加上 $k$。 $1\leq n,m\leq 10^5,-2\times 10^4\leq$ 每次加上的数和原序列的数 $\leq 2\times 10^4$。 …
LuoguP4119 [Ynoi2018] 未来日记
Description 题目链接:P4119 一个长为 $n$ 的序列 $a$,有 $m$ 次操作。 把区间 $[l,r]$ 内所有的 $x$ 变成 $y$。查询区间 $[l,r]$ 内第 $k$ 小值。 $1\leq n,m,a_i\leq 10^5$ Solution stO 陈指导 Orz,陈指导码了一个下午就做完了,蒟蒻我竟然写了3天。 首…
分块 学习笔记
前言 忽然发现分块大法很好用,然而本蒟蒻不会...所以心血来潮学习了分块 例题 Link Code [crayon-607acf6fee0ed496298127/]