首页 > 其他分享 >蒲公英

蒲公英

时间:2024-04-24 11:11:34浏览次数:12  
标签:le 询问 次数 众数 区间 蒲公英

[Violet] 蒲公英

题目背景

亲爱的哥哥:

你在那个城市里面过得好吗?

我在家里面最近很开心呢。昨天晚上奶奶给我讲了那个叫「绝望」的大坏蛋的故事的说!它把人们的房子和田地搞坏,还有好多小朋友也被它杀掉了。我觉得把那么可怕的怪物召唤出来的那个坏蛋也很坏呢。不过奶奶说他是很难受的时候才做出这样的事的……

最近村子里长出了一大片一大片的蒲公英。一刮风,这些蒲公英就能飘到好远的地方了呢。我觉得要是它们能飘到那个城市里面,让哥哥看看就好了呢!

哥哥你要快点回来哦!

爱你的妹妹 Violet

Azure 读完这封信之后微笑了一下。

“蒲公英吗……”

题目描述

在乡下的小路旁种着许多蒲公英,而我们的问题正是与这些蒲公英有关。

为了简化起见,我们把所有的蒲公英看成一个长度为 \(n\) 的序列 \(\{a_1,a_2..a_n\}\),其中 \(a_i\) 为一个正整数,表示第 \(i\) 棵蒲公英的种类编号。

而每次询问一个区间 \([l, r]\),你需要回答区间里出现次数最多的是哪种蒲公英,如果有若干种蒲公英出现次数相同,则输出种类编号最小的那个。

注意,你的算法必须是在线的

输入格式

第一行有两个整数,分别表示蒲公英的数量 \(n\) 和询问次数 \(m\)。

第二行有 \(n\) 个整数,第 \(i\) 个整数表示第 \(i\) 棵蒲公英的种类 \(a_i\)。

接下来 \(m\) 行,每行两个整数 \(l_0, r_0\),表示一次询问。输入是加密的,解密方法如下:

令上次询问的结果为 \(x\)(如果这是第一次询问,则 \(x = 0\)),设 \(l=((l_0+x-1)\bmod n) + 1,r=((r_0+x-1) \bmod n) + 1\)。如果 \(l > r\),则交换 \(l, r\)。
最终的询问区间为计算后的 \([l, r]\)。

输出格式

对于每次询问,输出一行一个整数表示答案。

样例 #1

样例输入 #1

6 3 
1 2 3 2 1 2 
1 5 
3 6 
1 5

样例输出 #1

1 
2 
1

提示

数据规模与约定

  • 对于 \(20\%\) 的数据,保证 \(n,m \le 3000\)。
  • 对于 \(100\%\) 的数据,保证 \(1\le n \le 40000\),\(1\le m \le 50000\),\(1\le a_i \le 10^9\),\(1 \leq l_0, r_0 \leq n\)。

题解

(开始接受洛谷自带Markdown)

分块好题! 求众数,由于众数不具有区间结合律(众数无法由几个众数求出),因此考虑分块暴力。

离散化后开始桶装暴力,预处理。

查询比较好想,先零散块,再整块。

  1. 预处理出每两个块间的众数,然后整个区间的众数只可能是中间整块的众数或是边缘零散块的数。

    遍历每一个块作为起点,往后找每一个数出现次数,并且把这个数所在块作为终点,更新。

  2. 维护用 \(vector\) 存每一个数出现的位置,用 \(upper_bound\) 和 \(lower_bound\) 找出下标做差,即为出现次数。

    注意这里是 \(upper_bound\) ,减出来刚好是区间长度。如求 \(x\) 在 \([l,r]\)的出现次数,

    正常写的时候应该是 \((r-l+1)\) ,如果第 \(r\) 位置正好有 \(x\),那么会找到 \((r+1)\) ,

    如果没有会找到比他大的那个,这时最后一个小于 \(x\) 的下标为 \(r\),则找到 \((r+1)\)。

注意

分块求前缀和或类似的区间值很方便,可以以块为单位记录。注意优化。

标签:le,询问,次数,众数,区间,蒲公英
From: https://www.cnblogs.com/ppllxx/p/18154637

相关文章

  • P4168 [Violet] 蒲公英 (莫队的强制在线)
    前言当个乐子看就行所用时间不如分块正解快虽然在线莫队实质也是分块[Violet]蒲公英题目背景亲爱的哥哥:你在那个城市里面过得好吗?我在家里面最近很开心呢。昨天晚上奶奶给我讲了那个叫「绝望」的大坏蛋的故事的说!它把人们的房子和田地搞坏,还有好多小朋友也被它杀掉了。我......
  • P4168 [Violet] 蒲公英(题解)
    题目题目描述输入格式输出格式数据范围![]样例输入:63123212153615输出:121思路暴力本题求区间内的最小众数,容易想到去用数组sum[i]表示第i种花的个数,在去便利比较,但是复杂度nm一定会T,这时候就要对暴力进行优化。分块优化1如果我们将所......
  • 蒲公英(分块)
    [Violet]蒲公英题目背景亲爱的哥哥:你在那个城市里面过得好吗?我在家里面最近很开心呢。昨天晚上奶奶给我讲了那个叫「绝望」的大坏蛋的故事的说!它把人们的房子和田地搞坏,还有好多小朋友也被它杀掉了。我觉得把那么可怕的怪物召唤出来的那个坏蛋也很坏呢。不过奶奶说他是很难受......
  • Ybt 金牌导航 6.3.A. 区间众数 / P4168 [Violet] 蒲公英(分块)
    题意简述多次查询区间\([l,r]\)的众数,若有多个取数值最小的。强制在线。\(n\le4\times10^4,m\le5\times10^4\)。分析考虑分块。首先预处理出块区间内的众数\(maj_{l,r}\)和每种数在某个块的前缀的出现次数\(cnt_{i,a_i}\),时空复杂度都是\(O(n\sqrtn)\)的。对于询......
  • html5页面飘落蒲公英动画特效代码
    超酷炫html5页面飘落蒲公英动画特效代码<!DOCTYPEhtmlPUBLIC"-//W3C//DTDXHTML1.0Transitional//EN""http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"><htmlxmlns="http://www.w3.org/1999/xhtml"><head><metaht......
  • 蒲公英
    这里主要是讲一下如何预处理以及时间复杂度的计算首先来看方法一预处理时,最外层循环是\(i\),第二层循环是\(j\),表示第\(i\)个块到第\(j\)个块先讲一下区间众数如何维护,记\(sum[i]\)表示\(i\)这个数出现的次数假设此时已经维护好了\([i,j]\)这些块的众数(记为\(most\)),而且也维护......
  • Luogu P4168 [Violet] 蒲公英 题解
    题目链接[Violet]蒲公英分析可以先将\(a[i]\)离散化然后考虑分块对于询问\(x,y\),\(x\)属于\(p\),\(y\)属于\(q\)当\(q-p<=1\)时直接暴力枚举即可,时间复杂度为\(O(\sqrt{n})\)\(else\)如图中间为分好块的地方我们发现,\(ans\)只可能为中间的众数或两边的......
  • 更新了蒲公英自动打包 出问题了
    今天重新更新了一下fastlane 和 plugin-pgyer  自动打包整么都上传不上去了 ipa包到是打包成功了,当时也没有多余的时间去研究问题 直接删除fastlane 重新下载 或者多次更新plugin-pgyer 还是一样报错fastlanefinishedwitherrors[!]Couldnotfindoption......
  • uniapp 打iOS测试包 到蒲公英进行分发测试
    使用Uniapp打iOS测试包并分发到蒲公英进行测试在移动应用开发中,我们通常需要将我们的应用打包成测试包进行测试。对于Uniapp开发的应用程序,我们可以使用一些工具来帮助我们打包iOS测试包,然后将其分发到蒲公英等平台进行测试。本文将为您介绍如何使用Uniapp打iOS测试包并分发到蒲公......
  • 蒲公英(Loj 分块模板9)
    [Violet]蒲公英题目背景亲爱的哥哥:你在那个城市里面过得好吗?我在家里面最近很开心呢。昨天晚上奶奶给我讲了那个叫「绝望」的大坏蛋的故事的说!它把人们的房子和田地搞坏,还有好多小朋友也被它杀掉了。我觉得把那么可怕的怪物召唤出来的那个坏蛋也很坏呢。不过奶奶说他是很难受......