fork(5) download
copy 
  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
comments (?)
stdin
copy 
10 3
-1 -1 1 1 1 1 3 10 10 10
2 3
1 10
5 10
0
stdout
copy 
1
4
3
https://ideone.com/EHUyPY
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!