fork(4) download
  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <vector>
  4. using namespace std;
  5. #define REP(i,n) for(int i=0;i<(n);i++)
  6. #define FOR(i,a,b) for(int i=(a);i<=(b);i++)
  7. #define FORD(i,a,b) for(int i=(a);i>=(b);i--)
  8.  
  9. int nextint()
  10. {
  11. int t;
  12. scanf("%d",&t);
  13. return t;
  14. }
  15.  
  16. struct info
  17. {
  18. int lv,rv;
  19. int lc,rc;
  20. int res;
  21. };
  22.  
  23. info merge(info l, info r)
  24. {
  25. if(l.res==0) return r;
  26. if(r.res==0) return l;
  27. info res;
  28. res.res=max(l.res,r.res);
  29. if(l.rv==r.lv)
  30. res.res=max(res.res,l.rc+r.lc);
  31. res.lv=l.lv;
  32. if(l.lv==r.lv)
  33. res.lc=l.lc+r.lc;
  34. else
  35. res.lc=l.lc;
  36. res.rv=r.rv;
  37. if(l.rv==r.rv)
  38. res.rc=l.rc+r.rc;
  39. else
  40. res.rc=r.rc;
  41. return res;
  42. }
  43.  
  44. vector<info> tree;
  45.  
  46. int ds;
  47.  
  48. int getds(int n)
  49. {
  50. n--;
  51. n|=n>>1;
  52. n|=n>>2;
  53. n|=n>>4;
  54. n|=n>>8;
  55. n|=n>>16;
  56. return n+1;
  57. }
  58.  
  59. int get(int l,int r)
  60. {
  61. info resl, resr;
  62. resl.lc=0; resl.rc=0; resl.res=0;
  63. resr.lc=0; resr.rc=0; resr.res=0;
  64. l+=ds;
  65. r+=ds;
  66. while(l<=r)
  67. {
  68. if(l&1) resl=merge(resl,tree[l++]);
  69. if(~r&1) resr=merge(tree[r--],resr);
  70. l>>=1;
  71. r>>=1;
  72. }
  73. return merge(resl,resr).res;
  74. }
  75.  
  76. int main()
  77. {
  78. while(1)
  79. {
  80. int n;
  81. int m;
  82. scanf("%d",&n);
  83. if(n==0) break;
  84. scanf("%d",&m);
  85. ds=getds(n);
  86. tree.resize(2*ds);
  87. REP(i,n)
  88. {
  89. int v;
  90. scanf("%d",&v);
  91. tree[i+ds].lv=tree[i+ds].rv=v;
  92. tree[i+ds].lc=tree[i+ds].rc=tree[i+ds].res=1;
  93. }
  94. FORD(i,ds-1,1)
  95. tree[i]=merge(tree[2*i],tree[2*i+1]);
  96. while(m--)
  97. {
  98. int l,r;
  99. scanf("%d%d",&l,&r);
  100. printf("%d\n",get(l-1,r-1));
  101. }
  102. }
  103. }
Success #stdin #stdout 0.02s 2864KB
stdin
16 1
1 1 1 1 2 2 2 3 3 2 2 2 4 4 4 4
1 16
0
stdout
4