fork(1) download
copy 
  1. // problem link : https://w...content-available-to-author-only...j.com/problems/FREQUENT/
  2.  
  3. #include <bits/stdc++.h>
  4.  
  5. using namespace std;
  6.  
  7. const int N = 1e5+7;
  8. int q,n,l,r;
  9. int a[N];
  10.  
  11. struct node{
  12.     int ml;
  13.     int occMl;
  14.     int mr;
  15.     int occMr;
  16.     int occ;
  17.  
  18.     node()
  19.     {
  20.         ml=0;
  21.         occMl=0;
  22.         mr=0;
  23.         occMr=0;
  24.         occ=0;
  25.     }
  26.  
  27.     node(int l,int occl, int r,int occr, int o)
  28.     {
  29.         ml=l;
  30.         occMl=occl;
  31.         mr=r;
  32.         occMr=occr;
  33.         occ=o;
  34.     }
  35. };
  36.  
  37. node tree[4*N];
  38.  
  39. node mergee(node &l, node &r)
  40. {
  41.     node nd = node(l.ml,l.occMl, r.mr, r.occMr, max(l.occ, r.occ));
  42.  
  43.     if (l.mr == r.ml)
  44.         nd.occ = max(nd.occ,l.occMr+r.occMl);
  45.  
  46.     if (l.ml == r.ml)
  47.         nd.occMl+=r.occMl;
  48.  
  49.     if (r.mr == l.mr)
  50.         nd.occMr+=l.occMr;
  51.  
  52.     return nd;
  53. }
  54.  
  55. void build(int id=0, int ns=0, int ne=n-1)
  56. {
  57.     if (ns==ne)
  58.     {
  59.         tree[id]=node(a[ns],1,a[ns],1,1);
  60.         return ;
  61.     }
  62.  
  63.     int l=2*id+1;
  64.     int r=l+1;
  65.     int mid=(ns+ne)/2;
  66.  
  67.     build(l,ns,mid);
  68.     build(r,mid+1,ne);
  69.  
  70.     tree[id]=mergee(tree[l],tree[r]);
  71. }
  72.  
  73. node query(int qs, int qe, int id = 0, int ns=0, int ne=n-1)
  74. {
  75.     if (qs>ne || qe<ns)
  76.         return node();
  77.  
  78.     if (qs<=ns && ne<=qe)
  79.         return tree[id];
  80.  
  81.     int l=2*id+1;
  82.     int r=l+1;
  83.     int mid = (ns+ne)/2;
  84.  
  85.     node n1 = query(qs,qe,l,ns,mid);
  86.     node n2 = query(qs,qe,r,mid+1,ne);
  87.  
  88.     return mergee(n1,n2);
  89.  
  90. }
  91.  
  92.  
  93. int main()
  94. {
  95.     //freopen("a.txt", "r", stdin);
  96.     cin>>n>>q;
  97.  
  98.     for(int i=0 ; i<n ; i++)
  99.         cin>>a[i];
  100.  
  101.     build();
  102.     while(q--)
  103.     {
  104.         cin>>l>>r;
  105.         cout<<query(--l,--r).occ<<'\n';
  106.     }
  107.  
  108.     return 0;
  109.  
  110. }
  111.  
Success #stdin #stdout 0.01s 11284KB
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/hi5Pzy
language:
C++14 (gcc 8.3)
created:
3 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!