Language: C++

//header{{{
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
//#include<boost/multiprecision/cpp_int.hpp>
//#include<boost/math/common_factor_rt.hpp>
  
using namespace std;
//using namespace boost::multiprecision;  
//using namespace boost::math;

#define rep(i,n) for(int i=0;i<(n);++i)
#define reps(i,n) for(int i=1;i<=(n);++i)
#define all(x) (x).begin(),(x).end()
#define Fixed fixed << setprecision(12)
#define int int64_t
using pii = pair<int,int>;
constexpr int INF  = 0x3f3f3f3f;
constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr int mod1 = 1e9+7; 
constexpr int mod2 = 998244353;

template <class A, class B> inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }
template <class A, class B> inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }

template <class T> using min_heap = priority_queue<T,vector<T>,greater<T> >;
template <class T> using max_heap = priority_queue<T>;
template <class A, class B> using umap = unordered_map<A,B>;
  
inline int square(int a){ return a * a;}
inline int updiv(int a,int b){ return (a + b - 1) / b; }

constexpr int dx[] = {1,0,-1,0,1,1,-1,-1};
constexpr int dy[] = {0,-1,0,1,1,-1,-1,1};
//}}}

struct Mo {
  using ADD = function< void(int) >;
  using DEL = function< void(int) >;
  using REM = function< void(int) >;

  int width;
  vector< int > left, right, order;
  vector< bool > v;

  Mo(int N, int Q) : width((int) sqrt(N)), order(Q), v(N) {
    iota(begin(order), end(order), 0);
  }

  void add(int l, int r) { /* [l, r) */
    left.emplace_back(l);
    right.emplace_back(r);
  }

  void run(const ADD &add, const DEL &del, const REM &rem) {
    assert(left.size() == order.size());
    sort(begin(order), end(order), [&](int a, int b) {
      int ablock = left[a] / width, bblock = left[b] / width;
      if(ablock != bblock) return;
      if(ablock & 1) return;
      return;
    });
    int nl = 0, nr = 0;
    auto push = [&](int idx) {
      v[idx].flip();
      if(v[idx]) add(idx);
      else del(idx);
    };
    for(auto idx : order) {
      while(nl > left[idx]) push(--nl);
      while(nr < right[idx]) push(nr++);
      while(nl < left[idx]) push(nl++);
      while(nr > right[idx]) push(--nr);
      rem(idx);
    }
  }
};

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n, q;
    cin >> n >> q;

    vector<int> c(1e6), v(1e6), res(q);

    rep(i,n){
        cin >> c[i];
    }

    Mo mo(n, q);

    rep(i, q){
        int l, r;
        cin >> l >> r;
        mo.add(l-1, r);
    }

    int ret = 0;
    auto add = [&](int p){
        if(v[c[p]]++ == 0){
            ret++;
        }
    };
    auto del = [&](int p){
        if(v[c[p]]-- == 1){
            ret--;
        }
    };
    auto rem = [&](int p){
        res[p] = ret;
    };

    mo.run(add, del, rem);

    for(auto &&e : res){
        cout << e << '\n';
    }

    return 0;
}



Compiler output:
In file included from /usr/include/c++/14/bits/stl_algobase.h:71,
                 from /usr/include/c++/14/algorithm:60,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:51,
                 from a.cc:3:
/usr/include/c++/14/bits/predefined_ops.h: In instantiation of 'constexpr bool __gnu_cxx::__ops::_Iter_comp_iter<_Compare>::operator()(_Iterator1, _Iterator2) [with _Iterator1 = __gnu_cxx::__normal_iterator<long int*, std::vector<long int> >; _Iterator2 = __gnu_cxx::__normal_iterator<long int*, std::vector<long int> >; _Compare = Mo::run(const ADD&, const DEL&, const REM&)::<lambda(int64_t, int64_t)>]':
/usr/include/c++/14/bits/stl_algo.h:1777:14:   required from 'void std::__insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<long int*, vector<long int> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<Mo::run(const ADD&, const DEL&, const REM&)::<lambda(int64_t, int64_t)> >]'
 1777 |           if (__comp(__i, __first))
      |               ~~~~~~^~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1817:25:   required from 'void std::__final_insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<long int*, vector<long int> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<Mo::run(const ADD&, const DEL&, const REM&)::<lambda(int64_t, int64_t)> >]'
 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 = __gnu_cxx::__normal_iterator<long int*, vector<long int> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<Mo::run(const ADD&, const DEL&, const REM&)::<lambda(int64_t, int64_t)> >]'
 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 = __gnu_cxx::__normal_iterator<long int*, vector<long int> >; _Compare = Mo::run(const ADD&, const DEL&, const REM&)::<lambda(int64_t, int64_t)>]'
 4805 |       std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
      |       ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:56:9:   required from here
   56 |     sort(begin(order), end(order), [&](int a, int b) {
      |     ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   57 |       int ablock = left[a] / width, bblock = left[b] / width;
      |       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   58 |       if(ablock != bblock) return;
      |       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   59 |       if(ablock & 1) return;
      |       ~~~~~~~~~~~~~~~~~~~~~~
   60 |       return;
      |       ~~~~~~~
   61 |     });
      |     ~~   
/usr/include/c++/14/bits/predefined_ops.h:158:30: error: void value not ignored as it ought to be
  158 |         { return bool(_M_comp(*__it1, *__it2)); }
      |                       ~~~~~~~^~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/predefined_ops.h: In instantiation of 'bool __gnu_cxx::__ops::_Val_comp_iter<_Compare>::operator()(_Value&, _Iterator) [with _Value = long int; _Iterator = __gnu_cxx::__normal_iterator<long int*, std::vector<long int> >; _Compare = Mo::run(const ADD&, const DEL&, const REM&)::<lambda(int64_t, int64_t)>]':
/usr/include/c++/14/bits/stl_algo.h:1757:20:   required from 'void std::__unguarded_linear_insert(_RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<long int*, vector<long int> >; _Compare = __gnu_cxx::__ops::_Val_comp_iter<Mo::run(const ADD&, const DEL&, const REM&)::<lambda(int64_t, int64_t)> >]'
 1757 |       while (__comp(__val, __next))
      |              ~~~~~~^~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1785:36:   required from 'void std::__insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<long int*, vector<long int> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<Mo::run(const ADD&, const DEL&, const REM&)::<lambda(int64_t, int64_t)> >]'
 1785 |             std::__unguarded_linear_insert(__i,
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
 1786 |                                 __gnu_cxx::__ops::__val_comp_iter(__comp));
      |                                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1817:25:   required from 'void std::__final_insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<long int*, vector<long int> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<Mo::run(const ADD&, const DEL&, const REM&)::<lambda(int64_t, int64_t)> >]'
 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 = __gnu_cxx::__normal_iterator<long int*, vector<long int> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<Mo::run(const ADD&, const DEL&, const REM&)::<lambda(int64_t, int64_t)> >]'
 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 = __gnu_cxx::__normal_iterator<long int*, vector<long int> >; _Compare = Mo::run(const ADD&, const DEL&, const REM&)::<lambda(int64_t, int64_t)>]'
 4805 |       std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
      |       ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:56:9:   required from here
   56 |     sort(begin(order), end(order), [&](int a, int b) {
      |     ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   57 |       int ablock = left[a] / width, bblock = left[b] / width;
      |       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   58 |       if(ablock != bblock) return;
      |       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   59 |       if(ablock & 1) return;
      |       ~~~~~~~~~~~~~~~~~~~~~~
   60 |       return;
      |       ~~~~~~~
   61 |     });
      |     ~~   
/usr/include/c++/14/bits/predefined_ops.h:240:30: error: void value not ignored as it ought to be
  240 |         { return bool(_M_comp(__val, *__it)); }
      |                       ~~~~~~~^~~~~~~~~~~~~~
/usr/include/c++/14/bits/predefined_ops.h: In instantiation of 'bool __gnu_cxx::__ops::_Iter_comp_val<_Compare>::operator()(_Iterator, _Value&) [with _Iterator = __gnu_cxx::__normal_iterator<long int*, std::vector<long int> >; _Value = long int; _Compare = Mo::run(const ADD&, const DEL&, const REM&)::<lambda(int64_t, int64_t)>]':
/usr/include/c++/14/bits/stl_heap.h:140:48:   required from 'void std::__push_heap(_RandomAccessIterator, _Distance, _Distance, _Tp, _Compare&) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<long int*, vector<long int> >; _Distance = long int; _Tp = long int; _Compare = __gnu_cxx::__ops::_Iter_comp_val<Mo::run(const ADD&, const DEL&, const REM&)::<lambda(int64_t, int64_t)> >]'
  140 |       while (__holeIndex > __topIndex && __comp(__first + __parent, __value))
      |                                          ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_heap.h:247:23:   required from 'void std::__adjust_heap(_RandomAccessIterator, _Distance, _Distance, _Tp, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<long int*, vector<long int> >; _Distance = long int; _Tp = long int; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<Mo::run(const ADD&, const DEL&, const REM&)::<lambda(int64_t, int64_t)> >]'
  247 |       std::__push_heap(__first, __holeIndex, __topIndex,
      |       ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  248 |                        _GLIBCXX_MOVE(__value), __cmp);
      |                        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_heap.h:356:22:   required from 'void std::__make_heap(_RandomAccessIterator, _RandomAccessIterator, _Compare&) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<long int*, vector<long int> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<Mo::run(const ADD&, const DEL&, const REM&)::<lambda(int64_t, int64_t)> >]'
  356 |           std::__adjust_heap(__first, __parent, __len, _GLIBCXX_MOVE(__value),
      |           ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  357 |                              __comp);
      |                              ~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1593:23:   required from 'void std::__heap_select(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<long int*, vector<long int> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<Mo::run(const ADD&, const DEL&, const REM&)::<lambda(int64_t, int64_t)> >]'
 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 = __gnu_cxx::__normal_iterator<long int*, vector<long int> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<Mo::run(const ADD&, const DEL&, const REM&)::<lambda(int64_t, int64_t)> >]'
 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 =