BZOJ2724 [Violet 6]蒲公英 解题报告【数据结构】【分块】

2024-03-28 14:58

本文主要是介绍BZOJ2724 [Violet 6]蒲公英 解题报告【数据结构】【分块】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Description

Input

修正一下
l = (l_0 + x - 1) mod n + 1, r = (r_0 + x - 1) mod n + 1
Output

Sample Input
6 3
1 2 3 2 1 2
1 5
3 6
1 5
Sample Output
1
2
1
HINT

修正下:
n <= 40000, m <= 50000
解题报告
传说中这是一道分块的经典题。
我们不难看出,这道题要我们强制在线,加上只是查找众数没有更改,不方便合并区间,让人不由自主地想到了分块。那么这个题用分块怎么做呢?
我们又均值不等式得,分成sqrt(n)块时时间复杂度最低。我们先预处理出几个值:

-f[i][j] 存储这样一个pair:(第i到第j块分块出现的次数最多的数的次数,这个数的值的负值)。由于我们知道比较pair的最大值是先比first再比second,这样一来就可以保证这个数组是最优的。

-s[i][j] 代表前i块中j这个数出现的次数的和(前缀和)。

由于这个题不可能直接开一个筒来存储每一个数出现的次数,我们的方法是先将原数组排序,离散化,再将进行这些操作之前的这个数组每个元素的排名存储下来。往后我们存储次数的时候就直接存储排名,而非元素本身。
要点似乎就是这些,代码如下:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
using namespace std;
const int N=4e4;
const int M=350;
int n,m,blk,cnt;
int lasans;
int a[N+5],b[N+5],c[N+5],bl[N+5],L[M+5],R[M+5],s[M+5][N+5];
pair<int,int>f[M+5][M+5];
int temp[N+5];
int query(int lf,int rg)
{pair<int,int>ret=f[bl[lf]+1][bl[rg]-1];if(bl[lf]==bl[rg])//在同一块里边,暴力 {for(int i=lf;i<=rg;i++)temp[b[i]]=0;for(int i=lf;i<=rg;i++)ret=max(ret,make_pair(++temp[b[i]],-b[i]));}else//不再同一块里,答案要么就是f[bl[lf]+1][bl[rg]-1],要么就是不再上述块中的数在[lf,rg]中出现的次数 {for(int i=lf;i<=R[bl[lf]];i++)temp[b[i]]=s[bl[rg]-1][b[i]]-s[bl[lf]][b[i]];//左边的零头中的元素在整块内的个数 for(int i=L[bl[rg]];i<=rg;i++)temp[b[i]]=s[bl[rg]-1][b[i]]-s[bl[lf]][b[i]];//右边的零头中的元素在整块内的个数 for(int i=lf;i<=R[bl[lf]];i++)ret=max(ret,make_pair(++temp[b[i]],-b[i]));//左边的零头中的元素在查询区间内的个数for(int i=L[bl[rg]];i<=rg;i++)ret=max(ret,make_pair(++temp[b[i]],-b[i]));//右边的零头中的元素在查询区间内的个数}return -ret.second;
}
int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%d",&a[i]),b[i]=a[i];sort(a+1,a+1+n);a[0]=unique(a+1,a+1+n)-a-1;//离散化 for(int i=1;i<=n;i++)b[i]=lower_bound(a+1,a+1+a[0],b[i])-a;//在b数组中存储排名 blk=sqrt(n);if(n%blk)cnt=n/blk+1;else cnt=n/blk;for(int i=1;i<=n;i++)bl[i]=(i-1)/blk+1;for(int i=1;i<=cnt;i++)L[i]=(i-1)*blk+1,R[i]=i*blk;R[cnt]=n;for(int i=1;i<=cnt;i++){memset(c,0,sizeof(c));pair<int,int>now(0,0);for(int j=L[i];j<=n;j++){c[b[j]]++;now=max(now,make_pair(c[b[j]],-b[j]));//计算出第i块到第j块的答案和他的值 f[i][bl[j]]=now;}for(int j=1;j<=a[0];j++)s[i][j]=s[i-1][j];for(int j=L[i];j<=R[i];j++)s[i][b[j]]++;//前缀和 }while(m--){int l,r;scanf("%d%d",&l,&r);int lf=(l+lasans-1)%n+1,rg=(r+lasans-1)%n+1;if(lf>rg)swap(lf,rg);lasans=a[query(lf,rg)];//返回的只是排名 printf("%d\n",lasans);}return 0;
}

这篇关于BZOJ2724 [Violet 6]蒲公英 解题报告【数据结构】【分块】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/855924

相关文章

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

【专题】2024飞行汽车技术全景报告合集PDF分享(附原数据表)

原文链接: https://tecdat.cn/?p=37628 6月16日,小鹏汇天旅航者X2在北京大兴国际机场临空经济区完成首飞,这也是小鹏汇天的产品在京津冀地区进行的首次飞行。小鹏汇天方面还表示,公司准备量产,并计划今年四季度开启预售小鹏汇天分体式飞行汽车,探索分体式飞行汽车城际通勤。阅读原文,获取专题报告合集全文,解锁文末271份飞行汽车相关行业研究报告。 据悉,业内人士对飞行汽车行业

6.1.数据结构-c/c++堆详解下篇(堆排序,TopK问题)

上篇:6.1.数据结构-c/c++模拟实现堆上篇(向下,上调整算法,建堆,增删数据)-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小): 2.2 C语言代码(手写堆) 2.3 C++代码(使用优先级队列 priority_queue)

计算机毕业设计 大学志愿填报系统 Java+SpringBoot+Vue 前后端分离 文档报告 代码讲解 安装调试

🍊作者:计算机编程-吉哥 🍊简介:专业从事JavaWeb程序开发,微信小程序开发,定制化项目、 源码、代码讲解、文档撰写、ppt制作。做自己喜欢的事,生活就是快乐的。 🍊心愿:点赞 👍 收藏 ⭐评论 📝 🍅 文末获取源码联系 👇🏻 精彩专栏推荐订阅 👇🏻 不然下次找不到哟~Java毕业设计项目~热门选题推荐《1000套》 目录 1.技术选型 2.开发工具 3.功能

《数据结构(C语言版)第二版》第八章-排序(8.3-交换排序、8.4-选择排序)

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多,算法平均时间性能比直接插入排序差。当初始记录无序,n较大时, 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In

Python:豆瓣电影商业数据分析-爬取全数据【附带爬虫豆瓣,数据处理过程,数据分析,可视化,以及完整PPT报告】

**爬取豆瓣电影信息,分析近年电影行业的发展情况** 本文是完整的数据分析展现,代码有完整版,包含豆瓣电影爬取的具体方式【附带爬虫豆瓣,数据处理过程,数据分析,可视化,以及完整PPT报告】   最近MBA在学习《商业数据分析》,大实训作业给了数据要进行数据分析,所以先拿豆瓣电影练练手,网络上爬取豆瓣电影TOP250较多,但对于豆瓣电影全数据的爬取教程很少,所以我自己做一版。 目

开题报告中的研究方法设计:AI能帮你做什么?

AIPaperGPT,论文写作神器~ https://www.aipapergpt.com/ 大家都准备开题报告了吗?研究方法部分是不是已经让你头疼到抓狂? 别急,这可是大多数人都会遇到的难题!尤其是研究方法设计这一块,选定性还是定量,怎么搞才能符合老师的要求? 每次到这儿,头脑一片空白。 好消息是,现在AI工具火得一塌糊涂,比如ChatGPT,居然能帮你在研究方法这块儿上出点主意。是不

【408数据结构】散列 (哈希)知识点集合复习考点题目

苏泽  “弃工从研”的路上很孤独,于是我记下了些许笔记相伴,希望能够帮助到大家    知识点 1. 散列查找 散列查找是一种高效的查找方法,它通过散列函数将关键字映射到数组的一个位置,从而实现快速查找。这种方法的时间复杂度平均为(

浙大数据结构:树的定义与操作

四种遍历 #include<iostream>#include<queue>using namespace std;typedef struct treenode *BinTree;typedef BinTree position;typedef int ElementType;struct treenode{ElementType data;BinTree left;BinTre

【干货分享】基于SSM的体育场管理系统的开题报告(附源码下载地址)

中秋送好礼 中秋佳节将至,祝福大家中秋快乐,阖家幸福。本期免费分享毕业设计作品:《基于SSM的体育场管理系统》。 基于SSM的体育场管理系统的开题报告 一、课题背景与意义 随着全民健身理念的深入人心,体育场已成为广大师生和社区居民进行体育锻炼的重要场所。然而,传统的体育场管理方式存在诸多问题,如资源分配不均、预约流程繁琐、数据统计不准确等,严重影响了体育场的使用效率和用户体验。