首页 > 其他分享 >P4119 [Ynoi2018] 未来日记

P4119 [Ynoi2018] 未来日记

时间:2023-12-07 17:34:04浏览次数:32  
标签:Ynoi2018 le text P4119 查询 值域 散块 日记

\(\text{Links}\)

LuoguBlog

P4119 [Ynoi2018] 未来日记

题外话

  • 个人生涯中第一道独立通过的 Ynoi 大分块!!

  • 同时也是个人生涯中通过的第十道 Ynoi 系列题目!!

  • 卡了好久结果加了个优化就过了/yun

  • AC 那一瞬间的场面好像 56 Seconds Later/ll

  • 感觉 \(8.5\) 的评分还是有点虚高(,个人体感 \(7\)。


题意

  • 将区间内的所有 \(x\) 变成 \(y\)

  • 查询区间第 \(k\) 小

\(1\le n,m,a_i\le 10^5\)


题解

首先考虑静态区间第 \(k\) 小怎么做。

可以二分答案,然后查询区间内 \(\le x\) 的数量,\(O(n\sqrt n\log n)\)。

套个值域分块,分别记录序列上前 \(i\) 个块中 \(j\) 的出现次数和第 \(j\) 个值域块中的值的出现次数之和。查询时先把散块的信息处理出来,再扫值域块 \(O(1)\) 累加次数,确定答案在哪个值域块,然后进入答案块中继续 \(O(1)\) 累加次数,直到加到 \(\ge k\) 就找到了答案。

然后考虑修改,维护上面提到的那些信息都很简单,把之前的 \(cnt_x\) 求出来,然后往后暴力更新就好了。

但是散块的查询就会比较难整,那么考虑怎样查询每个位置的值。

结合上修改操作,再加上第二分块赋予的经验,不难想到用并查集维护,在每个块内把相同颜色的位置并在一起,修改的时候整块直接把 \(x\) 并给 \(y\),散块暴力重构就好了。查询散块的时候直接 \(\text{find}\) 每个位置的值就好。

\(O(n\alpha(n)\sqrt n)\)。


进入正题 卡常

  • 块长稍微开大一点吧,大概不低于 \(300\),本人 AC 的时候取的是 \(400\)。

  • 修改操作暴力重构散块的时候,忽略除了 \(x\) 和 \(y\) 以外的值!本人就是靠这个优化 AC 的!

  • 同块内的查询直接 \(\text{nth-element}\)。

  • \(\text{fread + cout}\)

标签:Ynoi2018,le,text,P4119,查询,值域,散块,日记
From: https://www.cnblogs.com/MrcFrst-LRY/p/17883494.html

相关文章

  • 12.6日记
    JFinal是一款基于Java语言的轻量级、高性能的MVC框架,它在功能上延续了传统的JavaWeb开发框架的优点,同时也具有简洁的设计和强大的扩展性。以下是JFinal框架的主要功能和特点:MVC架构:JFinal遵循经典的MVC(Model-View-Controller)设计模式,将应用程序分为模型(Model)、......
  • 将json数据导入到ES集群——解决方案对比&填坑日记
    需求将写好的json数据。导入到es集群数据说明文件JSON数据,一行一个JSON。{"id":"d2716ae8fba4e026c4bd9445c3f49e2c","lang":"zh","title":"吉美旅馆","content":"吉美..."}{"id":"d2716ae8fba4e026c4bd9445......
  • 12.5日记
    普通创建:hadoopfs-mkdir/xiaolin递归创建:hadoopfs-mkdir-p/xiaolin/xiaoyin2)从本地剪切文件粘贴到HDFS上(-moveFromLocal)mkdirxuan.txthadoopfs-moveFromLocalxuan.txt/xiaolin3)把本地文件复制到HDFS上(-copyFromLocal或者-put)hadoopfs-copyFromLocalxuan.txt......
  • 大二快乐日记11.1
    JavaScript作为一种客户端脚本语言,可以在浏览器中实现输入验证判断,以保证用户输入的数据符合预期的格式和要求。下面介绍几种实现输入验证判断的方法。表单验证表单验证是最常用的输入验证方法之一。通过在表单元素上添加验证规则,比如必填项、格式限制等,可以在用户提交表单之前......
  • 12.3日记
    imread()读取图像cv.imread(filename[,flags])ImreadModes.Color:始终将图像转换为3通道BGR彩色图像,默认方式ImreadModes.Grayscale:始终将图像转换为单通道灰度图像ImreadModes.Unchanged:按原样返回加载的图像(使用Alpha通道)ImreadModes.AnyDepth:在输入具有相应深度时返回16位/3......
  • 12.2日记
    Scala是一门以Java虚拟机(JVM)为运行环境并将面向对象和函数式编程的最佳特性结合在一起的静态类型编程语言(静态语言需要提前编译的如:Java、C、C++等,动态语言如:JS)。1)Scala是一门多范式的编程语言,Scala支持面向对象和函数式编程。(多范式,就是多种编程方法的意思。有面向过程、面......
  • 2023.12.02 日记
    今天abc一定是有史以来打得最好的一次。排名居然高于CHD。虽然王教授和赖爷没打。我在48min写完了A~F题。然后50min想不出G。最终的排名是142。可惜D题没有认真看数据范围导致了一次罚时,不然排名会更高。当时看到G题感觉很惊悚,我很难很快地消去长度这一个无穷项......
  • 日记记录--小感动-感动-记录
    也让我从最近的经历提出来,总会被人讨厌,也会被人所感动,其实也没那么差,坚持自信放光芒。 顽石y: 下班,今天竟然莫名其妙被感谢被感动,因为自己微小的举动而被他人记录和感动,于我而言微小的举动却被他人放大和记录,真的很难得感觉,形成了互相感动的过程,,特地记录。  22:26 2回应......
  • 【自反】心理日记番外篇-Re:从零开始的补课生活
    注:以下内容所写均为当日手写的无意义内容,大家谨慎观看,不保证有发癫情节,有不适者请及时退出。【中國翻譯】(C82)一❤起❤补❤课28p【全彩】.7z点击查看目录目录2023/11/192023/11/202023/11/212023/11/222023/11/232023/11/242023/11/252023/11/262023/11/282023/11/292023/11......
  • 12.1日记
    令牌桶算法这里使用Redis实现令牌桶算法,令牌桶算法具体细节可参考其他博客,这里不赘述,大致就是在一个时间段内,存在一定数量的令牌,我们需要拿到令牌才可以继续操作。所以实现思路大致就是:   Redis中记录上次拿取令牌的时间,以及令牌数,每个手机号对应一个桶   每次拿令牌时......