fork(3) download
  1. #include <bits/stdc++.h>
  2.  
  3. typedef long long ll;
  4. using namespace std;
  5.  
  6. #define all(x) x.begin(), x.end()
  7. #define f(i,a,b) for(int i = (a); i <= (b); i++)
  8. #define fd(i,a,b) for(int i = (a); i >= (b); i--)
  9. #define mp make_pair
  10. #define faster_io() ios_base::sync_with_stdio(false)
  11. #define pb push_back
  12. #define pii pair<int,int>
  13. #define SZ(x) ((int)x.size())
  14. #define TRACE(x) cout << #x << " = " << x << "\n";
  15. #define vii vector<pair<int,int>>
  16.  
  17. const ll INF = 1000000005;
  18. const ll INFLL = 1000000000000000005ll;
  19. const ll MOD = 1000000007;
  20.  
  21. // --------------------------------------------------------------------------
  22.  
  23. const int RIGHT = 131072;
  24. const int SIZE = 265000;
  25.  
  26. int A[SIZE], L[SIZE], R[SIZE], M[SIZE];
  27. int N, Q;
  28.  
  29. void build(int n, int a, int b)
  30. {
  31. if(a == b)
  32. {
  33. L[n] = R[n] = M[n] = 1;
  34. return;
  35. }
  36.  
  37. int mid = (a+b) / 2;
  38. build(2*n, a, mid);
  39. build(2*n+1, mid+1, b);
  40.  
  41. int sz = (b-a+1) / 2;
  42. L[n] = L[2*n] == sz && A[mid] == A[mid+1] ? L[2*n] + L[2*n+1] : L[2*n];
  43. R[n] = R[2*n+1] == sz && A[mid] == A[mid+1] ? R[2*n] + R[2*n+1] : R[2*n+1];
  44. M[n] = max(max(max(M[2*n], M[2*n+1]), L[n]), R[n]);
  45. if(A[mid] == A[mid+1]) M[n] = max(M[n], R[2*n] + L[2*n+1]);
  46. }
  47.  
  48. int query(int l, int r, int n, int a, int b)
  49. {
  50. if(a > r || b < l) return 0;
  51. if(a >= l && b <= r) return M[n];
  52.  
  53. int mid = (a+b) / 2;
  54. int ql = query(l, r, 2*n, a, mid);
  55. int qr = query(l, r, 2*n+1, mid+1, b);
  56.  
  57. if(r <= mid) return ql;
  58. if(l > mid) return qr;
  59.  
  60. int at_left = min(mid-l+1, R[2*n]);
  61. int at_right = min(r-mid, L[2*n+1]);
  62. int middle = A[mid] == A[mid+1] ? at_left + at_right : 0;
  63. return max(max(ql,qr), middle);
  64. }
  65.  
  66. int main()
  67. {
  68. while(true)
  69. {
  70. scanf("%d",&N);
  71. if(!N) return 0;
  72. scanf("%d",&Q);
  73. f(i,1,N) scanf("%d",&A[i]);
  74. build(1,1,RIGHT);
  75. while(Q--)
  76. {
  77. int l,r;
  78. scanf("%d%d",&l,&r);
  79. printf("%d\n", query(l,r,1,1,RIGHT));
  80. }
  81. }
  82. }
  83.  
Success #stdin #stdout 0s 7480KB
stdin
Standard input is empty
stdout
Standard output is empty