[UVA] 11235 - Frequent Values

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 11235 - Frequent Values
Source            : UVA Online Judge
Category          : Data Structure
Algorithm         : Segment Tree
Verdict           : Accepted

#include "bits/stdc++.h"  
  
using namespace std;  
  
static const int maxn = 100010;  
  
struct SegmentTree  
{  
      int maxCount;  
      int maxCountValue;  
      int startValue;  
      int countStartValue;  
      int endValue;  
      int countEndValue;  
  
      SegmentTree(int maxCount = 0, int maxCountValue = 0, int startValue = 0, int countStartValue = 0, int endValue = 0, int countEndValue = 0)  
            : maxCount(maxCount)  
            , maxCountValue(maxCountValue)  
            , startValue(startValue)  
            , countStartValue(countStartValue)  
            , endValue(endValue)  
            , countEndValue(countEndValue) {}  
  
  
      void assignLeaf(int x)  
      {  
            maxCount = 1;  
            maxCountValue = x;  
            startValue = x;  
            countStartValue = 1;  
            endValue = x;  
            countEndValue = 1;  
      }  
      void marge(const SegmentTree &lchild, const SegmentTree &rchild)  
      {  
            if (lchild.startValue == 0 or lchild.endValue == 0)  
            {  
                  maxCount = rchild.maxCount;  
                  maxCountValue = rchild.maxCountValue;  
                  startValue = rchild.startValue;  
                  countStartValue = rchild.countStartValue;  
                  endValue = rchild.endValue;  
                  countEndValue = rchild.countEndValue;  
                  return;  
            }  
            if (rchild.startValue == 0 or rchild.endValue == 0)  
            {  
                  maxCount = lchild.maxCount;  
                  maxCountValue = lchild.maxCountValue;  
                  startValue = lchild.startValue;  
                  countStartValue = lchild.countStartValue;  
                  endValue = lchild.endValue;  
                  countEndValue = lchild.countEndValue;  
                  return;  
            }  
            if (lchild.endValue == rchild.startValue)  
            {  
                  int cnt = lchild.countEndValue + rchild.countStartValue;  
                  maxCount = cnt;  
                  maxCountValue = lchild.endValue;  
                  if (maxCount < lchild.maxCount)  
                  {  
                        maxCount = lchild.maxCount;  
                        maxCountValue = lchild.maxCountValue;  
                  }  
                  if (maxCount < rchild.maxCount)  
                  {  
                        maxCount = rchild.maxCount;  
                        maxCountValue = rchild.maxCountValue;  
                  }  
                  startValue = lchild.startValue;  
                  countStartValue = lchild.countStartValue;  
                  if (lchild.startValue == rchild.startValue)  
                  {  
                        countStartValue = lchild.countStartValue + rchild.countStartValue;  
                  }  
                  endValue = rchild.endValue;  
                  countEndValue = rchild.countEndValue;  
                  if (rchild.endValue == lchild.endValue)  
                  {  
                        countEndValue = rchild.countEndValue + lchild.countEndValue;  
                  }  
                  return;  
            }  
            maxCount = lchild.maxCount;  
            maxCountValue = lchild.maxCountValue;  
            if (maxCount < rchild.maxCount)  
            {  
                  maxCount = rchild.maxCount;  
                  maxCountValue = rchild.maxCountValue;  
            }  
            startValue = lchild.startValue;  
            countStartValue = lchild.countStartValue;  
            endValue = rchild.endValue;  
            countEndValue = rchild.countEndValue;  
      }  
} Tree[maxn * 4];  
  
int arr[maxn];  
  
void build(int node, int a, int b)  
{  
      if (a == b) return void(Tree[node].assignLeaf(arr[a]));  
      int lchild = node * 2;  
      int rchild = lchild + 1;  
      int mid = (a + b) / 2;  
      build(lchild, a, mid);  
      build(rchild, mid + 1, b);  
      Tree[node].marge(Tree[lchild], Tree[rchild]);  
}  
  
SegmentTree query(int node, int a, int b, int i, int j)  
{  
      if (a > j or b < i) return SegmentTree();  
      if (a >= i and b <= j) return Tree[node];  
      int lchild = node * 2;  
      int rchild = lchild + 1;  
      int mid = (a + b) / 2;  
      SegmentTree p = query(lchild, a, mid, i, j);  
      SegmentTree q = query(rchild, mid + 1, b, i, j);  
      SegmentTree res;  
      res.marge(p, q);  
      return res;  
}  
  
signed main()  
{  
      ios_base::sync_with_stdio(false);  
      cin.tie(nullptr);  
      cout.tie(nullptr);  
  
      #ifndef ONLINE_JUDGE  
            freopen("in.txt", "r", stdin);   
      #endif // ONLINE_JUDGE  
  
      int n;  
      while (cin >> n)  
      {  
            if (n == 0) break;  
            int q;  
            cin >> q;  
            for (int i = 1; i <= n; i++) cin >> arr[i];  
            build(1, 1, n);  
            while (q--)  
            {  
                  int l, r;  
                  cin >> l >> r;  
                  if (l > r) swap(l, r);  
                  SegmentTree seg = query(1, 1, n, l, r);  
                  cout << seg.maxCount << '\n';  
            }  
      }  
}