UVa 11235 - Frequent values

// UVa 11235 - Frequent values

#include <iostream>
#include <vector>
using namespace std;

struct node {
	node *left, *right;
	int max_freq;
	int ini, fin;
	int mid;
};

int find(int a, int b, node *nd) {
	if (nd->right == NULL && nd->left == NULL)
		return min(nd->max_freq, min(b, nd->fin) - max(a, nd->ini) + 1);
	if (nd->ini == a && nd->fin == b)
		return nd->max_freq;
	if (nd->right == NULL || nd->mid >= b)
		return find(a, b, nd->left);
	if (nd->mid < a)
		return find(a, b, nd->right);
	int l = find(a, nd->mid, nd->left);
	int r = find(nd->mid + 1, b, nd->right);
	return max(l, r);
}

int main() {
	int n, q;
	while ((cin >> n >> q) && n) {
		int b;
		node *nd = new node;
		vector<node*> this_lvl;
		nd->ini = 1;
		nd->max_freq = 1;
		for (int i = 1; i <= n; i++) {
			int a;
			cin >> a;
			if (i > 1 && a == b)
				nd->max_freq++;
			else if (i > 1 && a != b) {
				nd->fin = i - 1;
				nd->mid = 0;
				nd->left = NULL;
				nd->right = NULL;
				this_lvl.push_back(nd);
				nd = new node;
				nd->ini = i;
				nd->max_freq = 1;
			}
			b = a;
		}
		nd->fin = n;
		nd->mid = 0;
		nd->left = NULL;
		nd->right = NULL;
		this_lvl.push_back(nd);
		// build tree
		while (this_lvl.size() > 1) {
			vector<node*> next_lvl;
			for (int i = 0; i < this_lvl.size(); i += 2) {
				int j = (i + 1 < this_lvl.size()) ? i + 1 : i;
				node *nd = new node;
				nd->ini = this_lvl[i]->ini;
				nd->fin = this_lvl[j]->fin;
				nd->max_freq = max(this_lvl[i]->max_freq, this_lvl[j]->max_freq);
				nd->mid = this_lvl[i]->fin;
				nd->left = this_lvl[i];
				nd->right = (i != j) ? this_lvl[j] : NULL;
				next_lvl.push_back(nd);
			}
			this_lvl = next_lvl;
		}
		node* root = this_lvl[0];
		// queries
		for (; q; q--) {
			int a, b;
			cin >> a >> b;
			cout << find(a, b, root) << endl;
		}
	}
	return 0;
}