Uva 11235 Solution

Frequent values Solution

#include<bits/stdc++.h>

#define s start

#define e end

#define mx 100010

#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

using namespace std;

int a[mx], tree[mx*3], frequency[mx], firstindx[mx];

void initialize(int node, int s, int e)

{

    if(s == e)

    {

        tree[node] = frequency[s];

        return;

    }

    int left = node*2;

    int right = node*2+1;

    int mid = (s+e)/2;

    initialize(left, s, mid);

    initialize(right, mid+1, e);

    tree[node] = max(tree[left], tree[right]);

}

int query(int node, int s, int e, int i, int j)

{

    if(i>e || j<s)

        return 0;

    else if(s>=i && e<=j)

        return tree[node];

    int left = node*2;

    int right = node*2+1;

    int mid = (s+e)/2;

    int r1 = query(left, s, mid, i, j);

    int r2 = query(right, mid+1, e, i, j);

    return max(r1, r2);

}

int main()

{

    fast

    int n, q;

    while(cin >> n && n != 0)

    {

        cin >> q;

        map<int, int>mp;

        for(int i=1;i<=n;i++)

        {

            cin >> a[i];

            mp[a[i]]++;

        }

        int indx = -1;

        for(int i=1;i<=n;i++)

        {

            frequency[i] = mp[a[i]];

            if(i == 1)

                indx = i;

            else if(a[i] != a[i-1])

                indx = i;

            firstindx[i] = indx;

        }

        initialize(1, 1, n);

        int i, j;

        while(q--)

        {

            cin >> i >> j;

            if(a[i] == a[j])

                cout << j-i+1 << "\n";

            else

            {

                int first = frequency[i] + firstindx[i];

                int last = firstindx[j] - 1;

                int c1 = first - i;

                int c2 = j - firstindx[j] + 1;

                int c3 = query(1, 1, n, first, last);

                cout << max(c1, max(c2, c3)) << "\n";

            }

        }

    }

    return 0;

}