标签: 分块

10 篇文章

CF765F Souvenirs
Description 题目链接:CF765F 给定一个长度为 $n$ 的序列 $a_i$,有 $m$ 个询问,每次询问给定 $l,r$,求对于 $i,j\in[l,r]$,且满足 $i\not = j$,$|a_i - a_j|$ 的最小值。 $1\leq n\leq 10^5,1\leq m\leq 3\times 10^5,0\leq a_i…
SP11444 MAXOR – MAXOR & bzoj 2741 【FOTILE模拟赛】L
Description 给定一个长度为 $n$ 的序列 $a_i$,有 $m$ 个询问,查询一段区间内的子区间的异或和最大值。 强制在线。 $1\leq n\leq 10^5$ Solution 首先肯定考虑使用 Trie 树。 然而普通 Trie 树并不能处理这个问题,所以我们考虑先使其可持久化,处理区间异或值。 然后再分块,记 $F[i][j]…
P6774 [NOI2020] 时代的眼泪
Description 题目链接:P6774 给定长度为 $n$ 的序列,其中第 $i$ 个点的权值为 $p_i$,保证 $p_i$ 为 $[1,n]$ 的排列。 有 $m$ 个询问,每个询问给定 $l,r,x,y$ 表示求出序列区间为 $[l,r]$ 的矩形的值在 $[x,y]$ 的顺序对数量。 $n\leq 10^5,m\leq 2\times…
bzoj2122 工作评估
Description 题目链接:bzoj2122 利用空闲时间,BX希望外出工作,工作开始之前,公司就会给BX一个评估值 $X_0$,之后每天BX的评估值都是根据上一天的评估值和当天公司的运行状况得出,即 $X_i=X_{i-1}+D_i$,但是每天的评估值有一个上限,也就是说完整的评估公式应该是 $X_i=\min{X_i-1+D_i,L_i}…
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$。 …