input
1<=n,q<=100000
升序序列a1 a2 a3 ... an -100000<=ai<=100000
q行i j 1<=i,j<=n
输入结束标志n=0
output
对于每行i,j输出区间[i,j]中出现最多的数的个数
RMQ问题，处理的时候要合并区间
1 #include <cstdio> 2 #include <queue> 3 #include <cstring> 4 #include <iostream> 5 #include <cstdlib> 6 #include <algorithm> 7 #include <vector> 8 #include <map> 9 #include <set> 10 11 using namespace std; 12 13 int a[100010][2],b[100010][2],n,q,d[100010][20];//a[i][0]是第i个数，a[i][1]是第i个数在b数组中的下标，b[i][0]是开始的下标，b[1][1]是连续的个数 14 15 void RMQ_init() 16 { 17 for(int i=0;i<n;i++) 18 d[i][0]=1; 19 for(int j=1;(1<<j)-1<n;j++) 20 for(int i=0;i+(1<<j)-1<n;i++) 21 { 22 int i1=i+(1<<(j-1)); 23 d[i][j]=max(d[i][j-1],d[i1][j-1]); 24 if(a[i1-1][1]==a[i1][1])//区间中间合并 25 { 26 //printf("i=%d j=%d d=%d ",i,j,d[i][j]); 27 int beg,end,idx=a[i1][1]; 28 beg=max(b[idx][0],i); 29 end=min(b[idx][0]+b[idx][1]-1,i+(1<<j)-1); 30 //printf("beg=%d end=%d ",beg,end); 31 d[i][j]=max(d[i][j],end-beg+1); 32 //printf("d=%d ",d[i][j]); 33 } 34 } 35 } 36 37 int RMQ(int l,int r) 38 { 39 int k=0; 40 while((1<<(k+1))<=r-l+1) k++; 41 int maxd,beg,end,idx=r-(1<<k)+1; 42 maxd=max(d[l][k],d[idx][k]); 43 //区间合并 44 beg=max(b[a[idx][1]][0],l); 45 end=min(b[a[idx][1]][0]+b[a[idx][1]][1]-1,r); 46 //printf("beg=%d end=%d ",beg,end); 47 return max(maxd,end-beg+1); 48 } 49 50 int main() 51 { 52 freopen("/home/user/桌面/in","r",stdin); 53 while(scanf("%d",&n)==1&&n) 54 { 55 scanf("%d",&q); 56 memset(b,0,sizeof(b)); 57 scanf("%d",&a[0][0]); 58 int j=0; 59 a[0][1]=0; 60 b[0][0]=0; 61 b[0][1]=1; 62 for(int i=1;i<n;i++) 63 { 64 scanf("%d",&a[i][0]); 65 if(a[i][0]==a[i-1][0]) 66 { 67 b[j][1]++; 68 a[i][1]=j; 69 } 70 else 71 { 72 j++; 73 b[j][0]=i; 74 b[j][1]++; 75 a[i][1]=j; 76 } 77 } 78 //for(int i=0;i<n;i++) printf("%d %d ",a[i][0],a[i][1]); 79 //for(int i=0;i<=j;i++) printf("%d %d ",b[i][0],b[i][1]); 80 RMQ_init(); 81 for(int i=0,l,r;i<q;i++) 82 { 83 scanf("%d%d",&l,&r); 84 printf("%d ",RMQ(l-1,r-1)); 85 } 86 } 87 return 0; 88 }