1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 5 #include <cmath> 6 #include <algorithm> 7 using namespace std; 8  9 const int MAXN = 1e5 + 10;10 11 int a[MAXN], b[MAXN];12 int dp[MAXN][20];   // dp[i][j] 实质对应别人的F[i, j]13 14 //dp[i][j]: 从 i 起连续2^j个数中的最大值15 void makeRMQ(int n, int b[])16 {17     for (int i = 0; i < n; i++)18     {19         dp[i][0] = b[i];20 //        printf("dp[%d][0] = %d\n", i, dp[i][0]);21     }22     for (int j = 1; (1<<j) <= n; j++)  // 2*j <= n23     {24         for (int i = 0; i+(1<<j)-1 < n; i++)  // i+2*j-1 <= n25         {26     //        printf("before: dp[%d][%d] = %d, dp[%d][%d] = %d\n", i, j-1, dp[i][j-1], i+(1<<(j-1)), j-1, dp[i+(1<<(j-1))][j-1]);27             dp[i][j] = max(dp[i][j-1], dp[i+(1<<(j-1))][j-1]);   // F[i, j]=max（F[i，j-1], F[i + 2^(j-1)，j-1]）28     //        printf("after: dp[%d][%d] = %d\n", i, j, dp[i][j]);29         }30     }31 }32 33 int rmq(int s, int v)34 {35     int k = (int)(log(v-s+1.0) / log(2.0));36     return max(dp[s][k], dp[v-(1<<k)+1][k]);  // RMQ(A, i, j)=min{F[i,k],F[j-2^k+1,k]}37     // k=[log2(j-i+1)]38 }39 40 int find(int s, int t)   // 找到序列a中（下标从0开始）和a[t]（下标从1开始）值相同的第一个数（从左往右）的下标41 {                        // 例如对于 3 7， 返回的是6，因为a[7] = 3，和3相等的原始序列第一次出现3的时候下标是6（从0开始）42     int tmp = a[t];      // 再例如对于2 6，返回的是2，因为a[6] = 1，第一次出现1的时候是下标243     int l = s;44     int r = t;45     while (l < r)46     {47         int mid = ((l+r)>>1);48         if (a[mid] >= tmp)49             r = mid;50         else51             l = mid + 1;52     }53     return r;54 }55 56 int main()57 {58     int n, q, s, t;59     while (scanf("%d", &n) != EOF && n)60     {61         scanf("%d", &q);62         for (int i = 0; i < n; i++)63             scanf("%d", a+i);64         int tmp;65         for (int i = n-1; i >= 0; i--)66         {67             if (i == n-1)68                 tmp = 1;69             else70             {71                 if (a[i] == a[i+1])72                     tmp++;73                 else74                     tmp = 1;75             }76             b[i] = tmp;   // 代表从后往前数，连续相同的数有多少个77         }78         makeRMQ(n, b);79         while (q--)80         {81             scanf("%d%d", &s, &t);82             s--, t--;   // 下标从0开始83             int tmp = find(s, t);84             int ans = t - tmp + 1;85             t = tmp - 1;86         //    printf("ans = %d, t = %d\n", ans, t);87             if (s > t)88                 printf("%d\n", ans);      // 这个区间只有连续的一段数，例如 [2, 6] 只有[1 1 1 1]89             else90                 printf("%d\n", max(ans, rmq(s, t)));   // 要从两段区间里找(详细看链接)，因为这个区间有多个连续的一段数，例如[1, 10]有[1 1 1 1] 和[10 10 10]91         }92     }93     return 0;94 }