首页 > 代码库 > 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(线段树区间合并)