fork(4) download
  1. /*
  2. !----------------------------------------------------------------------------------------------------------------------------------------------------------------------
  3. ! ~ username : codephile
  4. ! ~ email : nvthanh1994@gmail.com
  5. !----------------------------------------------------------------------------------------------------------------------------------------------------------------------
  6. ! ~ Problems : 1684. Frequent values
  7. ! ~ Links :
  8. ! ~ Description :
  9. !----------------------------------------------------------------------------------------------------------------------------------------------------------------------
  10. */
  11.  
  12. #include <iostream>
  13. #include <algorithm>
  14. #include <cstdio>
  15. #include <cstring>
  16.  
  17. using namespace std;
  18.  
  19. #define inf 100000000
  20. #define mp make_pair
  21. #define x first // x ~ value
  22. #define y second // y ~ frequence
  23. #define N 100005
  24. typedef pair<int,int> pii;
  25.  
  26. struct node{
  27. pii M;
  28. pii l;
  29. pii r;
  30. };
  31.  
  32. node t[4*N];
  33. //------------------------- 1. Build Segment tree ---------------------------------------
  34. inline node combine(node a, node b){ // Combine two left son & right son interval
  35. node res;
  36. if(a.l.x==b.r.x){
  37. res.M.x=res.l.x=res.r.x=a.l.x;
  38. res.M.y=res.l.y=res.r.y=a.l.y+b.r.y;
  39. }
  40. else{
  41. // Update res.l, res.r
  42. res.l=a.l;
  43. res.r=b.r;
  44. if(a.l.x==b.l.x){
  45. res.l.y=a.l.y+b.l.y;
  46. }
  47. if(a.r.x==b.r.x){
  48. res.r.y=a.r.y+b.r.y;
  49. }
  50.  
  51. // Update res.M
  52. if(a.M.y>b.M.y) res.M=a.M;
  53. else res.M=b.M;
  54.  
  55. if(a.r.x==b.l.x){
  56. int temp=a.r.y+b.l.y;
  57. if(temp>res.M.y){
  58. res.M.x=a.r.x;
  59. res.M.y=temp;
  60. }
  61. }
  62. }
  63.  
  64. return res;
  65. }
  66.  
  67. // Clear
  68. void Util(){
  69. for(int i=0;i<4*N;i++){
  70. t[i].M.x=t[i].M.y=t[i].l.x=t[i].l.y=t[i].r.x=t[i].r.y=0;
  71. }
  72. }
  73.  
  74. // Build segment tree from a[tl]-> a[tr]
  75. void Build(int a[], int v, int tl, int tr){
  76. if(tl==tr){
  77. t[v].M=mp(a[tl],1);
  78. t[v].l=mp(a[tl],1);
  79. t[v].r=mp(a[tl],1);
  80. }
  81. else{
  82. int tm=(tl+tr)/2;
  83.  
  84. Build(a, v*2, tl, tm);
  85. Build(a, v*2+1, tm+1, tr);
  86.  
  87. t[v]=combine(t[v*2], t[v*2+1]);
  88. }
  89. }
  90.  
  91. //------------------------- 2. Main function of Segment tree ---------------------------------------
  92. inline node Query(int v, int tl, int tr, int l, int r){
  93. if(l==tl && (r==tr)) return t[v];
  94. int tm=(tl+tr)/2;
  95.  
  96. if(r<=tm) return Query(v*2,tl,tm,l,r);
  97. if(l>tm) return Query(v*2+1,tm+1,tr,l,r);
  98.  
  99. return combine(Query(v*2,tl,tm,l,tm),Query(v*2+1,tm+1,tr,tm+1,r));
  100. }
  101.  
  102. int main(){
  103.  
  104. int n,q,l,r;
  105. int a[N];
  106.  
  107. while(scanf("%d",&n)==1){
  108. if(n==0) break;
  109. scanf(" %d",&q);
  110. memset(a,0,sizeof a);
  111. for(int i=0; i<n; i++) scanf("%d",&a[i]);
  112. Util();
  113. Build(a,1,0,n-1);
  114. while(q--){
  115. scanf("%d %d",&l,&r);
  116. --l;
  117. --r;
  118. printf("%d\n",Query(1,0,n-1,l,r).M.y);
  119.  
  120.  
  121. }
  122. }
  123.  
  124.  
  125.  
  126.  
  127.  
  128.  
  129.  
  130.  
  131.  
  132.  
  133.  
  134.  
  135.  
  136. return 0;
  137. }
  138.  
Success #stdin #stdout 0.01s 13000KB
stdin
10 3
-1 -1 1 1 1 1 3 10 10 10
2 3
1 10
5 10
0
stdout
1
4
3