分类: oi

156 篇文章

LuoguP3604 美好的每一天
Description 题目链接:P3604 给定一个长度为 $n$ 的字符串(仅包含小写字母),有 $m$ 个询问区间 $[l,r]$,求区间的子区间重排能成为一个回文串的个数。 $1\leq n,m\leq 6\times 10^4$ Solution 数据范围较小,考虑莫队。 一个字符串重排能成为回文串的条件是出现次数最多有一个是奇数。 由于…
LuoguP3793 由乃救爷爷
Description 题目链接:P3793 给定一个 $n$ 个数的序列,有 $m$ 个询问,每次询问区间最大值。 $1\leq n,m\leq 2\times 10^7$,保证数据随机。 Solution 考虑分块。 如果朴素分块肯定是不能过的 $O(N\sqrt{N})$,但是这题并没有修改操作,所以考虑先预处理出第 $l$ 个块到第 $r$…
LuoguP3710 方方方的数据结构
Description 题目链接:P3710 给定一个长度为 $n$ 的序列,一开始序列的数全是 $0$,有 $m$ 个操作。 区间加区间乘单点查撤销第 $p$ 个操作(保证为加、乘操作) $1\leq n,m\leq 150000$,时间限制 $4s$,保证数据随机。 Solution 首先如果只有前 $3$ 个操作可以使用线段树。 然后考虑第 …
P4117 [Ynoi2018] 五彩斑斓的世界
Description 题目链接:P4117 给定一个长为 $n$ 的序列,有 $m$ 个操作: 区间 $[l,r]$ 中大于 $x$ 的数减去 $x$。查询区间 $[l,r]$ 中 $x$ 的出现次数。 $1\leq n \leq 10^6,1\leq m \leq 5\times 10^5,1\leq l \leq r\leq n,0\leq …
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天。 首…