Frequent values (线段树)
发布日期:2021-09-19 10:55:54 浏览次数:1 分类:技术文章

本文共 3326 字,大约阅读时间需要 11 分钟。

You are given a sequence of n integers a1, a2, . . . , an in non-decreasing order. In addition to that, you

are given several queries consisting of indices i and j (1 ≤ i ≤ j ≤ n). For each query, determine the
most frequent value among the integers ai
, . . . , aj .
Input
The input consists of several test cases. Each test case starts with a line containing two integers n and
q (1 ≤ n, q ≤ 100000). The next line contains n integers a1, . . . , an (−100000 ≤ ai ≤ 100000, for each
i ∈ {1, ..., n}) separated by spaces. You can assume that for each i ∈ {1, . . . , n − 1}: ai ≤ ai+1. The
following q lines contain one query each, consisting of two integers i and j (1 ≤ i ≤ j ≤ n), which
indicate the boundary indices for the query.
The last test case is followed by a line containing a single ‘0’.
Output
For each query, print one line with one integer: The number of occurrences of the most frequent value
within the given range.
Note: A naive algorithm may not run in time!
Sample Input
10 3
-1 -1 1 1 1 1 3 10 10 10
2 3
1 10
5 10
0
Sample Output
1
4
3

题目大概:

给出n个整数,求区间l,r之间的最多相同元素的数量,这n个整数满足(ai<=aj)当 i<=j 时。

思路:

看到这个题,就想把相同的元素合并成一个点,值为这个元素的数量,求最大相同元素个数,就是求最值。这样就转化为一个简单的线段树求区间最值的问题了。但是这个区间的端点需要特殊考虑一下,因为求得区间不一定是刚好是在每个元素的分界线上。这样,当区间很小时,也需要特殊考虑一下。

代码:

#include
#include
#include
#include
#include
using namespace std;#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1const int maxn=1e5+10;const int INF=0x3f3f3f3f;int Map[maxn];int a[maxn],b[maxn],c[maxn];int sum[maxn<<3];int cnt;void pushup(int rt){ sum[rt]=max(sum[rt<<1],sum[rt<<1|1]);}void build(int l,int r,int rt){ if(l==r) { sum[rt]=a[++cnt]; return; } int m=(l+r)>>1; build(lson); build(rson); pushup(rt);}int quert(int L,int R,int l,int r,int rt){ if(L<=l&&r<=R) { return sum[rt]; } int m=(l+r)>>1; int ret=0; if(L<=m)ret=max(ret,quert(L,R,lson)); if(R>m)ret=max(ret,quert(L,R,rson)); return ret;}int main(){ int n,m; while(~scanf("%d",&n)&&n) { memset(a,0,sizeof(a)); memset(c,0,sizeof(c)); memset(Map,0,sizeof(Map)); memset(b,0,sizeof(b)); memset(sum,0,sizeof(sum)); scanf("%d",&m); int u; cnt=0; int pre=INF; int ans=0; for(int i=1; i<=n; i++) { scanf("%d",&u); b[i]=u; if(u==pre) { Map[i]=ans; a[ans]++; c[i]=c[i-1]+1; } else { Map[i]=++ans; a[ans]++; c[i]=1; } pre=u; } build(1,ans,1); int l,r; for(int i=1; i<=m; i++) { scanf("%d%d",&l,&r); if(Map[l]==Map[r]) //区间只有一个点 { printf("%d\n",r-l+1); } else if(Map[r]-Map[l]==1)//区间有两个点,不需要用线段树 { printf("%d\n",max((a[Map[l]]-c[l]+1),c[r])); } else //区间有3个点以上,中间的点需要用线段树,两端特殊处理。 { int max_1=quert(Map[l]+1,Map[r]-1,1,ans,1); int max_2=a[Map[l]]-c[l]+1; int max_3=c[r]; int ma=max(max_1,max(max_2,max_3)); printf("%d\n",ma); } } } return 0;}

转载地址:https://blog.csdn.net/a1046765624/article/details/80752419 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:Flights (解方程)
下一篇:日记(周末)

发表评论

最新留言

留言是一种美德,欢迎回访!
[***.207.175.100]2024年03月27日 23时23分58秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

php rewrite url_PHP_URL Rewrite的设置方法,URL Rewrite需要服务器的支持! - phpStudy 2019-04-21
php读取大文件某行内容,PHP读取和修改大文件的某行内容_PHP教程 2019-04-21
打印php错误日志,php怎样打印错误日志 2019-04-21
Calendar导入java,Java程序使用Calendar.add()方法将分钟添加到当前时间 2019-04-21
mysql中用户线程作用,mysql用户线程的建立与用户线程的状态源码解析 2019-04-21
php页面引用公共文件,WeiPHP插件模板中快速引入公共模板文件 2019-04-21
php tracy,admin.php 2019-04-21
php访问父类的所有属性,php – 在父类中使用$this仅在子类中显示父类属性 2019-04-21
oracle比较强大的函数,SQL和ORACLE函数比较 2019-04-21
oracle12c order by,oracle 数据库中order by 的一些高级用法 2019-04-21
oracle8i substr,Oracle中的INSTR,NVL和SUBSTR函数的用法详解 2019-04-21
导出oracle11g的空表,轻松解决oracle11g 空表不能 exp 导出 的问题。 2019-04-21
php把整数拆分成数组,数组拆分处理(整数时的处理),该怎么处理 2019-04-21
oracle numlist,oracle sql str2numlist numtabletype 2019-04-21
php红包平均分配,红包平均分配算法 2019-04-21
linux磁盘的命令是,linux磁盘相关的命令 2019-04-21
linux服务器 缓存,Linux服务器内存使用分析及内存缓存 2019-04-21
linux查进程内存问题,关于linux 查看服务进程内存,cpu,内存占用的一些基础命令... 2019-04-21
linux英文包安装教程视频,Linux源码包安装过程讲解 2019-04-21
linux 关闭rsync服务器,linux下配置rsync服务器和实时同步 2019-04-21