fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef vector<int> vi;
  4.  
  5. struct node
  6. {
  7.     int Max; // maximum frequency
  8.     int prefixcount; // prefix of left element of array
  9.     int prefixnum; // left element of interval
  10.     int suffixcount; // right element freq
  11.     int suffixnum; // right element of interval
  12. };
  13.  
  14. typedef vector<node> vn;
  15.  
  16. node merge(node left, node right)
  17. {
  18.     node p;
  19.     if(left.suffixnum == right.prefixnum)
  20.     {
  21.         p.Max = max(left.Max, max(right.Max, left.suffixcount+right.prefixcount));
  22.         if(left.prefixnum == left.suffixnum)
  23.             p.prefixcount = left.prefixcount + right.prefixcount;
  24.         else
  25.             p.prefixcount = left.prefixcount;
  26.         if(right.prefixnum == right.suffixnum)
  27.             p.suffixcount = left.suffixcount + right.suffixcount;
  28.         else
  29.             p.suffixcount = right.suffixcount;
  30.     }
  31.     else
  32.     {
  33.         p.Max = max(left.Max, right.Max);
  34.         p.suffixcount = right.suffixcount;
  35.         p.prefixcount = left.prefixcount;
  36.     }
  37.     p.prefixnum = left.prefixnum;
  38.     p.suffixnum = right.suffixnum;
  39.     return p;
  40. }
  41.  
  42. node constTree(vn& tree, const vi& arr, int ss, int se, int si)
  43. {
  44.     if(ss==se)
  45.     {
  46.         tree[si].Max = tree[si].prefixcount = tree[si].suffixcount = 1;
  47.         tree[si].prefixnum = tree[si].suffixnum = arr[ss];
  48.         return tree[si];
  49.     }
  50.     int mid = ss + (se-ss)/2;
  51.     node left = constTree(tree, arr, ss, mid, 2*si+1);
  52.     node right = constTree(tree, arr, mid+1, se, 2*si+2);
  53.     tree[si] = merge(left, right);
  54.     return tree[si];
  55. }
  56.  
  57. node query(const vn& tree, const vi& arr, int ss, int se, int qs, int qe, int si)
  58. {
  59.     node p;
  60.     if(qs>se || qe<ss)
  61.         return p;
  62.     else if(qs<=ss && qe>=se)
  63.         return tree[si];
  64.     int mid = ss + (se-ss)/2;
  65.     if(qe<=mid)
  66.         return query(tree, arr, ss, mid, qs, qe, 2*si+1);
  67.     else if(mid<qs)
  68.         return query(tree, arr, mid+1, se, qs, qe, 2*si+2);
  69.     node left = query(tree, arr, ss, mid, qs, qe, 2*si+1);
  70.     node right = query(tree, arr, mid+1, se, qs, qe, 2*si+2);
  71.     return merge(left, right);
  72. }
  73.  
  74.  
  75. int main()
  76. {
  77.     int n, q, l, r;
  78.     scanf("%d %d", &n, &q);
  79.     vi arr(n);
  80.     for(int i=0; i<n; i++)
  81.         scanf("%d", &arr[i]);
  82.     vn tree(4*n);
  83.     constTree(tree, arr, 0, n-1, 0);
  84.     while(q--)
  85.     {
  86.         scanf("%d %d", &l, &r);
  87.         node p = query(tree, arr, 0, n-1, l-1, r-1, 0);
  88.         printf("%d\n", p.Max);
  89.     }
  90.     // scanf("%d", &l);
  91. }
Success #stdin #stdout 0s 15232KB
comments (?)
stdin
copy 
10 3
-1 -1 2 2 2 6 6 6 6 6
5 6
3 9
2 6
stdout
copy 
1
4
3
https://ideone.com/ks5nlh
language:
C++14 (gcc 8.3)
created:
6 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!