Language: C++

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define     ll          long long int
#define     REP(i,x,n)    for(ll i=x;i<n;i++)
#define     SZ(v)       (ll)v.size()
#define     endl        "\n"
#define     ff          first
#define     ss          second
#define     PQ_MIN      priority_queue <ll, vector<ll>, greater<ll> >
#define     PQ          priority_queue <int>
#define     pbds        tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define     setbit(x)   __builtin_popcount(x)
#define     prec(n)     fixed<<setprecision(n)
#define     pb(n)       push_back(n)
#define     mp(a,b)     make_pair(a,b)
#define     clr(n)      memset(n,0,sizeof(n))
#define     reset(n)    memset(n,-1,sizeof(n))
#define     ii          pair<ll,ll>
#define     vll         vector<ll>
using namespace std;
using namespace __gnu_pbds;
const ll INF=1e16;
const ll nxm=5e5+5;
ll a[nxm];
ll n,q;
ll query[nxm][3];
ll ans[nxm];
ll fre[nxm];
const ll rnxm=800;
ll cnt=0;



bool comp(ll a[3],ll b[3]) {
if(a[0]/rnxm==b[0]/rnxm)
    return a[1]<=b[1];
else
    a[0]/rnxm <=b[0]/rnxm;
}

void add(ll val)
{
    fre[val]++;
    if(fre[val]==1)
        cnt++;
}
void remo(ll val)
{
    fre[val]--;
    if(fre[val]==0)
        cnt--;
}

void solve(){




cin>>n>>q;

REP(i,0,n) cin>>a[i];



REP(i,0,q)
{

        cin>>query[i][0]>>query[i][1];
        query[i][2]=i;
        query[i][0]--,query[i][1]--;
}


sort(query,query+q,comp);

ll prevl=0,prevr=-1;

REP(i,0,q){


ll l=query[i][0],r=query[i][1];

while(l<prevl)
    prevl--,add(a[prevl]);

while(r>prevr)
    prevr++,add(a[prevr]);

while(prevl<l)
   remo(a[prevl]),prevl++;

while(prevr>r)
    remo(a[prevr]),prevr--;

ans[query[i][2]]=cnt;

}

REP(i,0,q) cout<<ans[i]<<endl;

















}
int main(){
//    freopen("timber_input", "r", stdin);
//    freopen("output.txt", "w", stdout);
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll t=1;
//	cin>>t;
    REP(i,1,t+1)
    {
//    cout<<"Case #"<<i<<": ";
		solve();
    }
	return 0;
}
//  bitset<64>(x).to_ullong() // in my com  _ulong()
//  cout<<bitset<64>(ans).to_string().substr(64-m)<<endl;
/*

char s[100];

fgets(s,100,stdin);

stringstream stram(s);

string abc;

bool ok1=0,ok2=0;

while(stram>>abc)
*/


Compiler output:
In file included from /usr/include/c++/14/algorithm:61,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:51,
                 from a.cc:1:
/usr/include/c++/14/bits/stl_algo.h: In instantiation of 'void std::__insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = long long int (*)[3]; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(long long int*, long long int*)>]':
/usr/include/c++/14/bits/stl_algo.h:1817:25:   required from 'void std::__final_insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = long long int (*)[3]; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(long long int*, long long int*)>]'
 1817 |           std::__insertion_sort(__first, __first + int(_S_threshold), __comp);
      |           ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1908:31:   required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = long long int (*)[3]; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(long long int*, long long int*)>]'
 1908 |           std::__final_insertion_sort(__first, __last, __comp);
      |           ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:4805:18:   required from 'void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = long long int (*)[3]; _Compare = bool (*)(long long int*, long long int*)]'
 4805 |       std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
      |       ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:75:5:   required from here
   75 | sort(query,query+q,comp);
      | ~~~~^~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1780:17: error: array must be initialized with a brace-enclosed initializer
 1780 |                 __val = _GLIBCXX_MOVE(*__i);
      |                 ^~~~~
/usr/include/c++/14/bits/stl_algo.h:1782:24: error: invalid array assignment
 1782 |               *__first = _GLIBCXX_MOVE(__val);
      |                        ^
In file included from /usr/include/c++/14/bits/stl_algo.h:61:
/usr/include/c++/14/bits/stl_heap.h: In instantiation of 'void std::__make_heap(_RandomAccessIterator, _RandomAccessIterator, _Compare&) [with _RandomAccessIterator = long long int (*)[3]; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(long long int*, long long int*)>]':
/usr/include/c++/14/bits/stl_algo.h:1593:23:   required from 'void std::__heap_select(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = long long int (*)[3]; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(long long int*, long long int*)>]'
 1593 |       std::__make_heap(__first, __middle, __comp);
      |       ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1868:25:   required from 'void std::__partial_sort(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = long long int (*)[3]; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(long long int*, long long int*)>]'
 1868 |       std::__heap_select(__first, __middle, __last, __comp);
      |       ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1884:27:   required from 'void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size, _Compare) [with _RandomAccessIterator = long long int (*)[3]; _Size = long int; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(long long int*, long long int*)>]'
 1884 |               std::__partial_sort(__first, __last, __last, __comp);
      |               ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1905:25:   required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = long long int (*)[3]; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(long long int*, long long int*)>]'
 1905 |           std::__introsort_loop(__first, __last,
      |           ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
 1906 |                                 std::__lg(__last - __first) * 2,
      |                                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 1907 |                                 __comp);
      |                                 ~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:4805:18:   required from 'void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = long long int (*)[3]; _Compare = bool (*)(long long int*, long long int*)]'
 4805 |       std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
      |       ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:75:5:   required from here
   75 | sort(query,query+q,comp);
      | ~~~~^~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_heap.h:355:22: error: array must be initialized with a brace-enclosed initializer
  355 |           _ValueType __value = _GLIBCXX_MOVE(*(__first + __parent));
      |                      ^~~~~~~
/usr/include/c++/14/bits/stl_heap.h: In instantiation of 'void std::__pop_heap(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Compare&) [with _RandomAccessIterator = long long int (*)[3]; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(long long int*, long long int*)>]':
/usr/include/c++/14/bits/stl_algo.h:1596:19:   required from 'void std::__heap_select(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = long long int (*)[3]; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(long long int*, long long int*)>]'
 1596 |           std::__pop_heap(__first, __middle, __i, __comp);
      |           ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1868:25:   required from 'void std::__partial_sort(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = long long int (*)[3]; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(long long int*, long long int*)>]'
 1868 |       std::__heap_select(__first, __middle, __last, __comp);
      |       ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1884:27:   required from 'void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size, _Compare) [with _RandomAccessIterator = long long int (*)[3]; _Size = long int; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(long long int*, long long int*)>]'
 1884 |               std::__partial_sort(__first, __last, __last, __comp);
      |               ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1905:25:   required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = long long int (*)[3]; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(long long int*, long long int*)>]'
 1905 |           std::__introsort_loop(__first, __last,
      |           ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
 1906 |                                 std::__lg(__last - __first) * 2,
      |                                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 1907 |                                 __comp);
      |                                 ~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:4805:18:   required from 'void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = long long int (*)[3]; _Compare = bool (*)(long long int*, long long int*)]'
 4805 |       std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
      |       ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:75:5:   required from here
   75 | sort(query,query+q,comp);
      | ~~~~^~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_heap.h:262:18: error: array must be initialized with a brace-enclosed initializer
  262 |       _ValueType __value = _GLIBCXX_MOVE(*__result);
      |                  ^~~~~~~
/usr/include/c++/14/bits/stl_heap.h:263:17: error: invalid array assignment
  263 |       *__result = _GLIBCXX_MOVE(*__first);
      |                 ^
a.cc: In function 'bool comp(long long int*, long long int*)':
a.cc:40:1: warning: control reaches end of non-void function [-Wreturn-type]
   40 | }
      | ^