uva11235

标签：const int max uva11235 include id

给一个非降序的排列{a}，多次询问区间 (l,r) 中出现次数最大的值，输出这个次数

 

比如 1 2 6 6 8 8 8 10 23 

相同的数据靠在一起，我们将相同数据组成一块（要处理出这个块的信息，比如左右端点

先查询中间的块的最大值（比如用st表) ，然后和两边的答案比较一下

 

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std ;
const int N=1e5+2;
//define int long long
 
 const int inf=1<<30;
 int st[N][20],n,a[N];
 
 int val[N],len[N],tot,L[N],R[N]; //block info
 int id[N];
 
 void init(){
     int i,j;
     for(i=1;i<=tot;i++) st[i][0]=len[i];
     for(j=1;j<20;j++)
      for(i=1;i+(1<<j)-1<=tot;i++){
          st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
      }
 }
 int q(int l,int r){
     int t=log2(r-l+1);
     return max(st[l][t],st[r-(1<<t)+1][t]);
 }
 
 void solve(){
     int i,j,x,y,Q;
     scanf("%d",&Q);
     a[0]=inf;
     tot=0;
     for(i=1;i<=n;i++){
         scanf("%d",a+i);
         if(a[i]==a[i-1]){
             len[tot]++; 
             id[i]=tot; 
         }
        else{
            R[tot]=i-1;
            tot++; len[tot]=1; val[tot]=a[i];
            L[tot]=i;
            id[i]=tot; 
        }
     }
     R[tot]=n;
     init();
     
     while(Q--){
         scanf("%d%d",&x,&y); 
         if(id[x]==id[y]){
             cout<<y-x+1<<endl;continue;
         }
         int t;
         if(id[x]+1>id[y]-1) t=0;
          else t= q(id[x]+1,id[y]-1);
         t=max(t,max(R[id[x]]-x+1,y-L[id[y]]+1));
         
         cout<<t<<endl;
     }
 }
 signed main(){
     //freopen("in","r",stdin); freopen("out","w",stdout);
     while(scanf("%d",&n),n) solve();
 }
 
 

 

标签：const,int,max,uva11235,include,id
From： https://www.cnblogs.com/towboa/p/16833359.html