网站首页
编程语言
数据库
系统相关
其他分享
编程问答
Ynoi2019
2024-01-24
P5048 [Ynoi2019 模拟赛] Yuno loves sqrt technology III(分块)
题意简述多次询问区间众数的出现次数,强制在线。\(n,m\le5\times10^5\),时限\(2\)秒,空限\(62.5\)MB。分析弱化版本题相较弱化版有以下特点:空间复杂度要求\(O(n)\)时间复杂度要求严格\(O(n\sqrtn)\),也就是说\(O(n\sqrt{n\logn})\)过不掉。貌似所有5e5的分块都是
2023-12-11
P5048 [Ynoi2019 模拟赛] 题解
题意给定\(n\)个数,有\(m\)个询问,每个询问给定\(l\)和\(r\),求出区间\(l\)到\(r\)中的最小众数出现次数,强制在线。数据范围:\(n\le500000\),空间限制:\(62.5MB\)。思路这道题的弱化版是蒲公英,这道题加强的地方在于数据范围。正常的分块求区间众数的空间复杂度是\(O(n
2023-12-07
P5048 [Ynoi2019 模拟赛] Yuno loves sqrt technology III
题意给定序列\(s\),每次询问\(l,r\)的区间众数的出现次数。强制在线。空间:\(62.5MB\)。Sol蒲公英卡常卡空间版。考虑优化那个\(n\timesm\)的数组。我们要求\(l,r\)之中某个数的个数。乍一看不好弄,仔细想想就会发现,如果我们知道当前的最优答案。在长常数时间内就
2023-09-29
P5047 [Ynoi2019 模拟赛] Yuno loves sqrt technology II 题解
Description给你一个长为\(n\)的排列,\(m\)次询问,每次查询一个区间的逆序对数,强制在线。link\(1\leqn,m\leq10^5\)。Solution考虑分块。首先如果\(l,r\)在同一个块内,可以对于每个块暴力二维前缀和预处理。如果\(l,r\)在不同的块内。设\(bel[l]=x,bel[r]=y\)。首
2023-07-11
P6109 [Ynoi2019] rprmq1
LuoguP6109[Ynoi2009]rprmq1LuoguP6109题目背景我谔谔本题读入量约13MB,输出量约7MB,请选择合适的输入输出方法题目描述有一个\(n\timesn\)的矩阵\(a\),初始全是\(0\),有\(m\)次修改操作和\(q\)次查询操作,先进行所有修改操作,然后进行所有查询操作。一次修改
2023-06-19
[Ynoi2019 模拟赛] Yuno loves sqrt technology I
题目Link分块,首先预处理所有整块之间的答案,这部分用类似莫队二离的手法可以改成\(O(n)\)次插入和\(O(n\sqrt{n})\)查询,然后根号平衡一手做到\(O(n\sqrt{n})\);空间自然也是能线性的。当然更直白的说法是,直接预处理\(f(i,j)\)表示前\(i\)块中\(>j\)的元素个数。然后考
2023-02-22
[ds 记录] P5046 [Ynoi2019 模拟赛] Yuno loves sqrt technology I
首Ynoi。这题用CF765F那个方法能做但是肯定慢得飞起(\(n\sqrt{n}\)个longlong)。这个方法挺依赖逆序对性质,比如可减性,以及方便通过值域上的前缀和求贡献。算法流程:
2023-01-15
【题解】P6578 [Ynoi2019] 魔法少女网站
卡了一晚上终于过了。好家伙,又是想题想一半不会是吧,小垃圾是不是想退役/fad小黑子->小垃圾->垃圾酱->垃圾摇滚/xk但是真的有垃圾摇滚这东西/kk思路操作分块
2022-12-30
Ynoi2019模拟赛题解
\(Ynoi2019\)模拟赛题解前言:第一次做\(Ynoi\)还是有被离谱到的,我从来没有做到过这么卡常的题目,我到现在\(T1\)都还是\(70\)分,\(lxl\)毒瘤名不虚传啊。但是不得不说,\(Ynoi