POJ3368 Frequent values（RMQ线段树）

题目大概说给一个递增序列，询问区间出现最多的数。

用莫队算法比较直观，虽然应该会T。。好像也可以主席树。。不过题目给的序列是有序的，因而相同的数会聚在一起。

考虑把序列分成一段一段，使每段都包含极大的相同的数字

这样对于每一个区间查询：

• • 可能这个区间左边或右边没有包含完整的一段，而其长度在段里对左或右端点进行二分查找就知道了
  • 而除去两边不完整的，还要求出中间若干完整段的最大长度，这个就是用RMQ来快速解决了

于是这题就能这样解决了。

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 #define MAXN 222222

 int lrec[MAXN],rrec[MAXN];

 int tree[MAXN<<],N,x,y;

 void update(int i,int j,int k){

     if(i==j){

         tree[k]=y;

         return;

     }

     int mid=i+j>>;

     if(x<=mid) update(i,mid,k<<);

     else update(mid+,j,k<<|);

     tree[k]=max(tree[k<<],tree[k<<|]);

 }

 int query(int i,int j,int k){

     if(x>y) return ;

     if(x<=i && j<=y){

         return tree[k];

     }

     int mid=i+j>>,res=;

     if(x<=mid) res=max(res,query(i,mid,k<<));

     if(y>mid) res=max(res,query(mid+,j,k<<|));

     return res;

 }

 int seq[MAXN];

 int main(){

     int n,q,a,b;

     while(~scanf("%d",&n) && n){

         scanf("%d",&q);

         for(int i=; i<=n; ++i){

             scanf("%d",seq+i);

         }

         seq[n+]=;

         int rn=;

         lrec[]=;

         for(int i=; i<=n+; ++i){

             if(seq[i]!=seq[i+]){

                 rrec[rn]=i;

                 rn++;

                 lrec[rn]=i+;

             }

         }

         memset(tree,,sizeof(tree));

         for(N=; N<rn; N<<=);

         for(int i=; i<rn; ++i){

             x=i; y=rrec[i]-lrec[i]+;

             update(,N-,);

         }

         int i,j,res;

         while(q--){

             scanf("%d%d",&a,&b);

             i=lower_bound(rrec,rrec+rn,a)-rrec;

             j=upper_bound(lrec,lrec+rn,b)-lrec-;

             if(rrec[i]>=b){

                 printf("%d\n",b-a+);

                 continue;

             }

             res=max(rrec[i]-a+,b-lrec[j]+);

             x=i+; y=j-;

             res=max(res,query(,N-,));

             printf("%d\n",res);

         }

     }

     return ;

 }