I tried to solve Fast Queries using Segment tree. I managed to initialize segment tree where each node contain number of distinct integers. But could not managed to build up query function.

suppose input is

1 1 1 2 3 5 2 1

if query is (4 8)

then node number 11 & 3 are required. But from those, how can I find that array value of 4 & 7 are same?

My code

#include<stdio.h>
#include<iostream>
#include<ctype.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<string>
#include<algorithm>
#include<vector>
#include<sstream>
#include<stack>
#include<queue>
#include<map>
#include<set>
using namespace std;

const int SIZE=100005;
struct TT{
    int aa,bb;
};
int arr[SIZE],tree[SIZE*3];
TT brr[SIZE*3];
map<int,int>MP;
int t,cases,test,n,q,i,a,b,val;

int func(int m,int n){
    int i,t,asg=0;
    for(i=brr[m].aa;i<=brr[m].bb;i++){
        t=arr[i];
        if(MP.find(t)==MP.end()) MP[t]=asg++;
    }
    for(i=brr[n].aa;i<=brr[n].bb;i++){
        t=arr[i];
        if(MP.find(t)==MP.end()) MP[t]=asg++;
    }
    t=MP.size();
    MP.clear();
    return t;
}

void find(int node,int low,int high){
    int mid,add,left,right;
    if(low==high){
        tree[node]=1;
        return;
    }
    left=node<<1;
    right=left+1;
    mid=(low+high)>>1;
    brr[left]={low,mid};
    brr[right]={mid+1,high};
    brr[node]={low,high};
    find(left,low,mid);
    find(right,mid+1,high);
    tree[node]=func(left,right);
}

int query(int node,int low,int high,int i,int j){
    if(i>high || j<low) return 0;
    if(low>=i && high<=j) return tree[node];
    int left,right,mid,temp,temp2,add;
    left=node<<1;
    right=left+1;
    mid=(low+high)>>1;
    temp=query(left,low,mid,i,j);
    temp2=query(right,mid+1,high,i,j);
    add=max(temp,temp2);
    return add;
}

int main()
{
    #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    #endif

    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&q);
        for(i=1;i<=n;i++)
            scanf("%d",&arr[i]);
        find(1,1,n);
        for(i=1;i<16;i++) printf("%d (%d %d) %d\n",i,brr[i].aa,brr[i].bb,tree[i]);
        printf("Case %d:\n",++cases);
        while(q--){
            scanf("%d%d",&a,&b);
            val=query(1,1,n,a,b);
            printf("%d\n",val);
        }
    }
    return 0;
}