题意
给出一串数字,有m次询问,每次询问[ab]区间内出现次数最多的数字出现了多少次。
思路
一开始用线段树+延迟标记超时到死,后来发现只用哈希+区间极值做就可以
例如 11111【1111222233444488】888 求【】内的时候就把区间内的串分为1111 2222334444 88对中间的串哈希+区间极值再和两边的串长度进行比较
#include<iostream> #include<cstring> #include<cstdio> #include<map> using namespace std; const int nMax = 100010; int num[nMax]; struct{ int l,r,val; }node[3*nMax]; map<int,pair<int,int> >mp; int has[nMax]; void build(int left ,int right ,int u){ node[u].l = left; node[u].r = right; if(left == right){ node[u].val = mp[left].second - mp[left].first + 1; return; } int m = (left + right) >> 1; build(left ,m ,2*u); build(m+1 ,right ,2*u + 1); node[u].val = max(node[2*u].val ,node[u*2 + 1].val); } int query(int left ,int right ,int u){ if(left == node[u].l && right == node[u].r){ return node[u].val; } int m = (node[u].l + node[u].r)>>1; if(right <= m){ return query(left ,right ,u*2); } if(left >= m+1){ return query(left ,right ,u*2 + 1); } int a = query(left ,m ,u*2 ); int b = query(m+1 ,right ,u*2 + 1); return max(a ,b); } int main(){ int n ,m ,a ,b ,i ,k; while(scanf("%d",&n)!=EOF && n){ scanf("%d",&m); num[0] = 100001; k=0; for(i = 1 ;i <= n ;i++ ){ scanf("%d",&num[i]); if(num[i] != num[i-1]){ has[i] = ++k; mp[k].first = i; mp[k].second = i; }else{ mp[k].second = i; has[i] = k; } } build(1 ,k ,1); while(m -- ){ scanf("%d%d",&a,&b); if(has[a] == has[b]){ printf("%d\n",b - a + 1); continue; } int la = mp[has[a]].second; int lb = mp[has[b]].first; if(lb == la + 1){ la = max(la - a + 1,b - lb + 1); printf("%d\n",la); continue; } int lc = query(has[a]+1 ,has[b] -1 ,1); la = max(lc ,max(la - a + 1,b - lb + 1)); printf("%d\n",la); // printf("%d\n",query(a ,b ,1)); } } return 0; }
//TLE代码 #include<iostream> #include<cstring> #include<cstdio> #include<map> using namespace std; const int nMax = 100010; int num[nMax]; struct{ int l,r,val,late; }node[3*nMax]; void build(int left ,int right ,int u){ node[u].l = left; node[u].r = right; node[u].late = 1; if(num[node[u].l] == num[node[u].r]){ node[u].late = 0; return; } int m =(node[u].l + node [u].r)>>1; build(node[u].l , m ,u*2); build(m + 1 ,node[u].r ,u*2 + 1); } map<int,pair<int,int> >mp; int query(int left ,int right ,int u){ if(node[u].late == 0 || num[left] == num[right]){ return right - left + 1; } int m =(node[u].l + node[u].r)>>1,aa; if(right <= m){ aa=query(left ,right ,u*2); // cout<<left<<" "<<right<<" "<<aa<<endl; return aa; } if(left >= m+1){ aa = query(left ,right ,u*2 + 1); // cout<<left<<" "<<right<<" "<<aa<<endl; return aa; } int a = query(left ,m ,u*2 ); int b = query(m + 1 ,right , u*2 + 1); if(num[m] == num[m+1]){ int la = max(mp[num[m]].first ,left); int lb = min(mp[num[m]].second ,right); // cout<<left<<" "<<right<<" "<<max((lb - la + 1),max(a,b))<<endl; return max((lb - la + 1),max(a,b)); }else{ // cout<<left<<" "<<right<<" "<<max(a,b)<<endl; return max(a,b); } } int main(){ int n ,m ,a ,b ,i; while(scanf("%d",&n)!=EOF && n){ scanf("%d",&m); num[0] = 100001; for(i = 1 ;i <= n ;i++ ){ scanf("%d",&num[i]); if(num[i] != num[i-1]){ mp[num[i]].first = i; mp[num[i]].second = i; }else{ mp[num[i]].second = i; } } build(1 ,n ,1); while(m -- ){ scanf("%d%d",&a,&b); printf("%d\n",query(a ,b ,1)); } } return 0; }
相关推荐
NULL 博文链接:https://128kj.iteye.com/blog/1740501
POJ2528-Mayor's posters 【区间映射压缩(离散化)+线段树】 解题报告+AC代码 http://hi.csdn.net/!s/83XZJU ========> 我的所有POJ解题报告链接: http://blog.csdn.net/lyy289065406/article/details/6642573
poj2823,使用线段树进行查询区域间最大最小值,线段树初步
这是一道很不错的题目,即可以用线段树做也可以用树状数组,可谓经典。不过当然了线段树是比较难搞,而树状数组是极其简洁的,构造很简单,下面就分别来介绍一下两种方法...
问题:求平面上多个矩形的总面积。 算法:线段树(经典的线段树题目)
NULL 博文链接:https://128kj.iteye.com/blog/1739064
NULL 博文链接:https://128kj.iteye.com/blog/1739733
大量线段树题目 zoj 1610 线段覆盖 poj 2777 线段覆盖 poj 2528 需要离散化,建树不同,需要处理不同->注意这组数据 3 1 10 1 3 6 10 the ans is 3. hdu 1754 求区间最大值 hdu 1166 求区间和 hdu 1698 成段更新 ...
线段树、树状数组算法入门 加 poj解题报告 pdf文档
poj 2763 程序 线段树 LCA 2000MS AC
POJ题解 个人写法 线段树每个人都不一样
NULL 博文链接:https://128kj.iteye.com/blog/1746750
大家都用树状数组,但是有人只会用线段树呢? 而且我可以轻易改出一道不能用树状数组的题 在线段树一次次TLE后,有一个ID发帖抱怨 “下次写一个汇编版非递归线段树,再超时?” 可是大家都知道,超时的代码已经2k了...
史上最全poj题目分类及原题 包括:基本算法:贪心、递归、递推、枚举;基本数据结构,链表、栈;动态规划;搜索;高级数据结构:二叉搜索树、线段树、树状数组;数学:数论
POJ1151 Atlantis的源代码,非常经典线段树应用的题目,求面积。
POJ3468,线段树处理,注意longlongint
此为本人在poj做过的经典题目的代码与一些经典数据结构算法的模板程序,如线段树,拓扑排序等
以每个星星为中心,得到可以罩住它的矩形的左下角的范围,这些范围内的点增加星星亮度,由于落在框上的点不算,框不一定要整数起点,可另左下落在框上算。求亮度和最大的点即可。...每次用线段树更新和求最大值。
acm code of 20053565 poj onlinejudge 高精度 DP 图论 算法 最大流 最小生成树 线段树
POJ 2182 引自余立功《算法训练教程》,线段树的应用