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天。 首…
LuoguP4593 [TJOI2018]教科书般的亵渎
Description 题目链接 小豆喜欢玩游戏,现在他在玩一个游戏遇到这样的场面,每个怪的血量为 $a_i$,且每个怪物血量均不相同,小豆手里有无限张“亵渎”。亵渎的效果是对所有的怪造成 $1$ 点伤害,如果有怪死亡,则再次施放该法术。我们认为血量为 $0$ 怪物死亡。 小豆使用一张 “亵渎”会获得一定的分数,分数计算如下,在使用一张“亵渎”之后…
bzoj3217 ALOEXT
Description 给定一个序列,有以下 $4$ 种操作: I x y 插入 $y$ 到第 $x$ 个之前。D x 删除第 $x$ 个元素。C x y 修改第 $x$ 个元素为 $y$。F l r 询问区间 $[l,r]$ 的次大值与区间一个数的异或最大值。 强制在线,$1\leq N,M \leq 10^5$。 Solution 这道题显然可…