Segment Tree (Range Maximum Query Along with Count of Maximum Element)

 #include<bits/stdc++.h>  
 #include "iostream"  
 using namespace std;  
 class node{  
 public:  
      int data;  
      int l,r;  
      int count;  
      node* left,*right;  
 };  
 node* newNode(int data,int l,int r){  
      node* newN = new node;  
      newN->data = data;  
      newN->l = l;  
      newN->r = r;  
      newN->count = 1;  
      return newN;  
 }  
 int operationOnData(int data1,int data2){  
      return max(data1,data2);  
 }  
 node* buildTree(int arr[],int l,int r)  
 {  
      if(l>r) return NULL;  
      node* nd;  
      if(l==r)  
           nd = newNode(arr[l],l,r);  
      else{  
           nd = newNode(0,l,r);  
           int mid = (l+r)/2;  
           nd->left = buildTree(arr,l,mid);  
           nd->right = buildTree(arr,mid+1,r);  
           nd->data = operationOnData(nd->left->data,nd->right->data);  
           if(nd->left->data==nd->right->data) nd->count = nd->left->count+nd->right->count;  
           else{  
                if(nd->left->data > nd->right->data) nd->count = nd->left->count;  
                else nd->count = nd->right->count;  
           }  
      }  
      return nd;  
 }  
 pair<int,int> getMax(node* root,int l, int r){  
      if(root->l>=l && root->r<=r){  
           return {root->data,root->count};  
      }  
      else  
      if(root->r<l ||root->l>r)  
           return {INT_MIN,0} ;   
      else{  
           pair<int,int> left = getMax(root->left,l,r);  
           pair<int,int> right = getMax(root->right,l,r);  
           if(left.first==right.first){  
                return {left.first,left.second+right.second};  
           }   
           else if(left.first>right.first){  
                return {left.first,left.second};  
           }  
           else   
                return{right.first,right.second};  
      }  
 }  
 int height(node* root)  
 {  
      if(root==NULL) return 0;  
      int lHeight = height(root->left);  
      int rHeight = height(root->right);  
      return lHeight>rHeight?lHeight+1:rHeight+1;  
 }  
 void printLevel(node* root,int d)  
 {  
      if(root==NULL) return;  
      if(d==1) cout<<root->data<<" "<<root->count<<" "<<root->l<<" "<<root->r<<endl;  
      printLevel(root->left,d-1);  
      printLevel(root->right,d-1);  
 }  
 void levelorder(node* root)  
 {  
      for(int d =1; d<=height(root) ;d++)  
           printLevel(root,d);  
 }  
 int main()  
 {  
       int n,m;  
       //cin>>n>>m;  
       n=5;m=1;  
       int arr[100000] = {3,1,3,2,1};  
       for(int i=0;i<n;i++);  
            //cin>>arr[i];  
       node* root = buildTree(arr,0,n-1);  
       while(m--){  
            int l,r;  
            //cin>>l>>r;  
            pair<int,int> p = getMax(root,l,r);  
            cout<<"Max Element is "<<p.first<<" and its Count in given range is ";  
            cout<<p.second<<endl;  
       }  
 }