月度归档: 2021年3月

8 篇文章

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 这道题显然可…
LuoguP2839 [国家集训队]middle
Description 题目链接 一个长度为 $n$ 的序列 $a$,设其升序排序之后为 $b$,那么序列 $a$ 的中位数定义为 $b_{\lfloor\frac{n}{2}\rfloor}$,其中 $a,b$ 从 $0$ 开始标号,除法取下整。 给你一个长度为 $n$ 的序列 $s$。回答 $Q$ 个这样的询问:$s$ 的左端点在 $[a,b]…
浅谈莫队
简介 莫队算法是由莫涛提出的算法。在莫涛提出莫队算法之前,莫队算法已经在 Codeforces 的高手圈里小范围流传,但是莫涛是第一个对莫队算法进行详细归纳总结的人。莫涛提出莫队算法时,只分析了普通莫队算法,但是经过 OIer 和 ACMer 的集体智慧改造,莫队有了多种扩展版本。莫队算法可以解决一类离线区间询问问题,适用性极为广泛。同时将其加以扩…
LuoguP3209 [HNOI2010] 平面图判定
Description 判定一个图是否为平面图的问题是图论中的一个重要问题。现在假设你要判定的是一类特殊的图是否是平面图,图中存在一个包含所有顶点的环,即存在哈密顿回路。 对于一个无向图 $G=(V,E)$,如果能够做到把它画在同一个平面上,使得 $\forall (a,b)(c,d)$,$a,b,c,d$ 两两不等的情况下,边 $(a,b)$ 和…
LuoguP3007 [USACO11JAN] The Continental Cowngress G
Description 给出 $n$ 个法案,$m$ 头牛的意见, 每头牛会表决两次。每次表决格式为 i Y 表示“支持 $i$ 号法案”或 i N 表示“反对 $i$ 号法案”。最终,每头牛至少要有一个表决被满足。不可能成立的话输出 IMPOSSIBLE,否则输出方案。 $1\leq N \leq 1,000,1\leq M \leq 4,000…