poj 3368 Frequent values

線段樹，每個節點記錄lmax,rmax,max 左邊頻率最高，右邊頻率最高，整體的頻率最高。   這樣就可以由子區間組合出答案。       #include <iostream>   #include <cstdio> #include <cstring> using namespace std; #define ls t<<1 #define rs t<<1|1 #define midt (tr[t].l+tr[t].r)>>1 const int maxn=1e5+9; int a[maxn]; int n,q;     struct {     int l,r,max,lmax,rmax,sum; }tr[maxn<<2];     void maketree(int t,int l,int r) {     tr[t].l=l;     tr[t].r=r;     tr[t].sum=r-l+1;     if(l==r)     {         tr[t].lmax=tr[t].rmax=tr[t].max=1;         return;     }     int mid=midt;     maketree(ls,l,mid);     maketree(rs,mid+1,r);     tr[t].lmax=tr[ls].lmax;     if(tr[ls].lmax==tr[ls].sum&&a[tr[ls].r]==a[tr[rs].l])     tr[t].lmax+=tr[rs].lmax;         tr[t].rmax=tr[rs].rmax;     if(tr[rs].rmax==tr[rs].sum&&a[tr[rs].l]==a[tr[ls].r])     tr[t].rmax+=tr[ls].rmax;         tr[t].max=max(tr[t].lmax,tr[t].rmax);     tr[t].max=max(tr[ls].max,tr[t].max);     tr[t].max=max(tr[t].max,tr[rs].max);     if(a[mid]==a[mid+1])     tr[t].max=max(tr[t].max,tr[ls].rmax+tr[rs].lmax); }     int query(int t,int l,int r) {     int mid=midt;     if(tr[t].l==l&&tr[t].r==r)     return(tr[t].max);         if(r<=mid)     return(query(ls,l,r));     else if(mid+1<=l)     return(query(rs,l,r));     else     {         int ret=max(query(ls,l,mid),query(rs,mid+1,r));         if(a[mid]==a[mid+1])         {             int lmax=min(tr[rs].lmax,r-mid);             int rmax=min(tr[ls].rmax,mid-l+1);             ret=max(ret,lmax+rmax);         }         return(ret);     } }     int main() {     while(scanf("%d %d",&n,&q),n)     {         for(int i=1;i<=n;i++)         scanf("%d",&a[i]);         maketree(1,1,n);         for(int i=1,l,r;i<=q;i++)         {             scanf("%d %d",&l,&r);             printf("%d\n",query(1,l,r));         }     }     return 0; }