首页 > 代码库 > POJ 3368 Frequent values(线段树区间合并)
POJ 3368 Frequent values(线段树区间合并)
【题目链接】 http://poj.org/problem?id=3368
【题目大意】
有一个有序序列,要求区间查询出现次数最多的数
【题解】
维护每个区间左端点和右端点,以及左右的长度,还有区间的答案
每次线段合并的时候,对区间数据进行合并即可。
【代码】
#include <cstdio>#include <algorithm>using namespace std;const int N=100010;struct data{int a,b,l,r,val;}T[N*4];int num[N],n,q,l,r;data combine(data &l,data &r){ data ans; ans.a=l.a; ans.b=r.b; ans.l=l.a==r.a?l.l+r.l:l.l; ans.r=r.b==l.b?l.r+r.r:r.r; ans.val=max(l.val,r.val); if(l.b==r.a)ans.val=max(ans.val,l.r+r.l); return ans;}void build(int x,int l,int r){ if(l==r){T[x]=(data){num[l],num[r],1,1,1};return;} int mid=(l+r)>>1; build(x<<1,l,mid);build(x<<1|1,mid+1,r); T[x]=combine(T[x<<1],T[x<<1|1]);}data query(int L,int R,int x,int l,int r){ if(r<L||R<l){data u;return u;} if(L<=l&&r<=R)return T[x]; int mid=(l+r)>>1; data vl=query(L,R,x<<1,l,mid),vr=query(L,R,x<<1|1,mid+1,r); if(mid<L)return vr; if(mid>=R)return vl; return combine(vl,vr);}int main(){ while(scanf("%d",&n)&&n){ scanf("%d",&q); for(int i=1;i<=n;i++)scanf("%d",&num[i]); build(1,1,n); while(q--){ scanf("%d%d",&l,&r); printf("%d\n",query(l,r,1,1,n).val); } }return 0;}
POJ 3368 Frequent values(线段树区间合并)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。