http://poj.org/problem?id=3368
题意：给出一个非降序排列的整数数组，对于询问（i，j），输出区间[i,j]中出现最多的值的次数。
思路：经典的RMQ，不过我用线段树做的。首先要离散化，因为是非降序的，所以相同的数是连续的，可以将相同的数分在同一个块中，将块中的信息存储起来，然后将其看成一个点，就可以用线段树进行查询了。
1 #include <stdio.h> 2 #include <string.h> 3 #include <algorithm> 4 using namespace std; 5 const int N=1000010; 6 struct node 7 { 8 int l,r; 9 int Max; 10 } Tree[N*4]; 11 struct point//记录每块的信息 12 { 13 int s,t;//s起始位置，t结束位置 14 int cnt;//块中的数出现的次数 15 } block[N]; 16 int v[N],num[N];//num[i]表示第i个数被分在第几块 17 void build(int l,int r,int rt) 18 { 19 Tree[rt].l = l; 20 Tree[rt].r = r; 21 if (l==r) 22 { 23 Tree[rt].Max = block[l].cnt; 24 return ; 25 } 26 int mid = (l+r)>>1; 27 build(l,mid,rt<<1); 28 build(mid+1,r,rt<<1|1); 29 Tree[rt].Max=max(Tree[rt<<1].Max,Tree[rt<<1|1].Max); 30 } 31 int Query(int l,int r,int rt) 32 { 33 if(Tree[rt].l==l&&Tree[rt].r==r) 34 return Tree[rt].Max; 35 int mid=(Tree[rt].l+Tree[rt].r)>>1; 36 if (r <= mid) 37 return Query(l,r,rt<<1); 38 else if (l > mid) 39 return Query(l,r,rt<<1|1); 40 else 41 return max(Query(l,mid,rt<<1),Query(mid+1,r,rt<<1|1)); 42 } 43 int main() 44 { 45 int n,q; 46 while(~scanf("%d%d",&n,&q)&&n) 47 { 48 memset(block,0,sizeof(block)); 49 for (int i = 1; i <= n; i++) 50 scanf("%d",&v[i]); 51 int m=1; 52 block[m].s=1; 53 for (int i = 1; i <= n; i++)//将相同的数分在同一块 54 { 55 num[i]=m; 56 if(v[i]!=v[i+1]||i==n) 57 { 58 block[m].t = i; 59 block[m].cnt=block[m].t-block[m].s+1; 60 block[++m].s = i+1; 61 } 62 } 63 build(1,m-1,1);//将每一块看成一个点，建树 64 while(q--) 65 { 66 int l,r; 67 scanf("%d%d",&l,&r); 68 if (num[l]==num[r])//在同一个块里，则[l,r]是连续的相同的数 69 printf("%d ",r-l+1); 70 else //不在同一个块里 71 { 72 int cnt1 = block[num[l]].t-l+1;//l所在块中，区间[l,block[num[l]].t]中相同的数的次数 73 int cnt3 = r-block[num[r]].s+1;//r所在块中，区间[block[num[r]].s,r]中相同的数的次数 74 int cnt2 = 0; 75 if (num[r]-num[l]>1)//大于两个块 76 cnt2 = Query(num[l]+1,num[r]-1,1);//中间块相同数出现的最多次数 77 int ans = max(max(cnt1,cnt3),cnt2); 78 printf("%d ",ans); 79 } 80 } 81 } 82 return 0; 83 }