Distinct numbers between a query

Problem Link: https://atcoder.jp/contests/abc174/tasks/abc174_e

Input:

10 10
2 5 6 5 2 1 7 9 7 2
5 5
2 4
6 7
2 2
7 8
7 9
1 8
6 9
8 10
6 8

Output:

1
2
2
1
2
2
6
3
3
3

#include<bits/stdc++.h>

using namespace std;

const int N = (int) 5e5 + 5;

struct query

{

    int l,r,id;

} q[N];

int a[N],k=1000,l=1,r=0;

bool compare(query &a,query &b)

{

    int b_a = a.l/k;

    int b_b = b.l/k;

    if(b_a==b_b)

        return a.r<b.r;

    return b_a<b_b;

}

int cnt[N],ans[N];

int res=0;

void add(int x)

{

    cnt[a[x]]++;

    if(cnt[a[x]]==1)

        ++res;

}

void remove(int x)

{

    cnt[a[x]]--;

    if(cnt[a[x]]==0)

        --res;

}

int main()

{

    int n,Q;

    cin>>n>>Q;

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

        cin>>a[i];

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

    {

        cin>>q[i].l>>q[i].r;

        q[i].id=i;

    }

    sort(q+1,q+Q+1,compare);

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

    {

        while(l > q[i].l)

            add(--l);

        while(r < q[i].r)

            add(++r);

        while(l < q[i].l)

            remove(l++);

        while(r > q[i].r)

            remove(r--);

        ans[q[i].id]=res;

    }

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

    {

        printf("%d\n", ans[i]);

    }

    return 0;

}