题意：
给出一个非降序排列的整数数组a1，a2，...，an，你的任务是对于一系列询问（i，j），回答ai，ai+1，...aj中出现次数最多的值所出现的次数。
思路：
首先对整个数组进行游程编码，比如（-1,1,1,2,2,2,4）就可以编码成（-1,1），（1,2），（2,3），（4,1），其中（a，b）表示有b个连续的a。
用count[i]表示第i段的出现次数，num[p]表示第p个数所在的段，left[i],right[i]表示第i段的左右坐标值。
1 #include2 #include 3 #include 4 using namespace std; 5 6 const int maxn = 100000 + 5; 7 8 int n, q, ret; 9 int a[maxn];10 int count[maxn];11 int num[maxn];12 int left[maxn];13 int right[maxn];14 int d[maxn][20];15 16 void RMQ_init()17 {18 for (int i = 1; i <= ret; i++)19 d[i][0] = ::count[i];20 for (int j = 1; (1 << j) <= ret;j++)21 for (int i = 1; i + (1 << j) <= ret; i++)22 d[i][j] = max(d[i][j - 1], d[i + (1 << (j-1))][j - 1]);23 }24 25 int RMQ(int L, int R)26 {27 int k = 0;28 while ((1 << (k + 1)) <= R - L + 1) k++;29 return max(d[L][k], d[R - (1 << k) + 1][k]);30 }31 32 int main()33 {34 //freopen("D:\\txt.txt", "r", stdin);35 while (cin >> n && n)36 {37 cin >> q;38 for (int i = 1; i <= n; i++)39 cin >> a[i];40 ret = 1;41 for (int i = 1; i <= n; i++)42 {43 num[i] = ret;44 ::left[ret] = i;45 int cnt = 1;46 while (a[i] == a[i + 1])47 {48 num[i + 1] = ret;49 cnt++;50 i++;51 }52 ::right[ret] = i;53 ::count[ret] = cnt;54 ret++;55 }56 RMQ_init();57 int L, R;58 int ans;59 for (int i = 0; i < q; i++)60 {61 cin >> L >> R;62 int k1 = num[L];63 int k2 = num[R];64 ans = 0;65 if (k1 == k2) cout << R - L + 1 << endl;66 else if (k2 - k1 == 1)67 {68 ans = max(::right[k1] - L + 1, R - ::left[k2] + 1);69 cout << ans << endl;70 }71 else72 {73 ans = max(::right[k1] - L + 1, R - ::left[k2] + 1);74 ans = max(ans, RMQ(k1+1, k2-1));75 cout << ans << endl;76 }77 }78 }79 }