Language: C++


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);
    }

    int 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 ablock < bblock;
            if(ablock & 1) return right[a] < right[b];
            return right[a] > right[b];
        });
        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);
        }
    }
};

int main() {
    int N, Q;
    cin >> N;
    cin >> Q;

    vector< int > A(N);
    for(int i = 0; i < N; i++) {
        cin >> A[i];
    }
    vector< int > f(1000001);

    Mo mo(N, Q);
    for(int i = 0; i < Q; i++) {
        int l, r;
        cin >> l >> r;
        mo.add(--l, r);
    }
    int ret = 0;
    auto add = [&](int idx) { if(f[A[idx]]++ == 0) ret++; };
    auto del = [&](int idx) { if(f[A[idx]]-- == 1) --ret; };
    vector< int > ans(Q);
    auto rem = [&](int idx) { ans[idx] = ret; };
    mo.run(add, del, rem);
    for(int i = 0; i < Q; i++) {
        cout << ans[i] << "\n";
    }
}


Compiler output:
a.cc:3:17: error: 'function' does not name a type; did you mean 'union'?
    3 |     using ADD = function< void(int) >;
      |                 ^~~~~~~~
      |                 union
a.cc:4:17: error: 'function' does not name a type; did you mean 'union'?
    4 |     using DEL = function< void(int) >;
      |                 ^~~~~~~~
      |                 union
a.cc:5:17: error: 'function' does not name a type; did you mean 'union'?
    5 |     using REM = function< void(int) >;
      |                 ^~~~~~~~
      |                 union
a.cc:8:5: error: 'vector' does not name a type
    8 |     vector< int > left, right, order;
      |     ^~~~~~
a.cc:9:5: error: 'vector' does not name a type
    9 |     vector< bool > v;
      |     ^~~~~~
a.cc:20:19: error: 'ADD' does not name a type
   20 |     int run(const ADD &add, const DEL &del, const REM &rem) {
      |                   ^~~
a.cc:20:35: error: 'DEL' does not name a type
   20 |     int run(const ADD &add, const DEL &del, const REM &rem) {
      |                                   ^~~
a.cc:20:51: error: 'REM' does not name a type
   20 |     int run(const ADD &add, const DEL &del, const REM &rem) {
      |                                                   ^~~
a.cc: In constructor 'Mo::Mo(int, int)':
a.cc:11:36: error: 'sqrt' was not declared in this scope
   11 |     Mo(int N, int Q) : width((int) sqrt(N)), order(Q), v(N) {
      |                                    ^~~~
a.cc:11:46: error: class 'Mo' does not have any field named 'order'
   11 |     Mo(int N, int Q) : width((int) sqrt(N)), order(Q), v(N) {
      |                                              ^~~~~
a.cc:11:56: error: class 'Mo' does not have any field named 'v'
   11 |     Mo(int N, int Q) : width((int) sqrt(N)), order(Q), v(N) {
      |                                                        ^
a.cc:12:20: error: 'order' was not declared in this scope
   12 |         iota(begin(order), end(order), 0);
      |                    ^~~~~
a.cc:12:14: error: 'begin' was not declared in this scope
   12 |         iota(begin(order), end(order), 0);
      |              ^~~~~
a.cc:12:28: error: 'end' was not declared in this scope
   12 |         iota(begin(order), end(order), 0);
      |                            ^~~
a.cc:12:9: error: 'iota' was not declared in this scope
   12 |         iota(begin(order), end(order), 0);
      |         ^~~~
a.cc: In member function 'void Mo::add(int, int)':
a.cc:16:9: error: 'left' was not declared in this scope
   16 |         left.emplace_back(l);
      |         ^~~~
a.cc:17:9: error: 'right' was not declared in this scope
   17 |         right.emplace_back(r);
      |         ^~~~~
a.cc: In member function 'int Mo::run(const int&, const int&, const int&)':
a.cc:21:16: error: 'left' was not declared in this scope
   21 |         assert(left.size() == order.size());
      |                ^~~~
a.cc:21:31: error: 'order' was not declared in this scope
   21 |         assert(left.size() == order.size());
      |                               ^~~~~
a.cc:21:9: error: 'assert' was not declared in this scope
   21 |         assert(left.size() == order.size());
      |         ^~~~~~
a.cc:1:1: note: 'assert' is defined in header '<cassert>'; this is probably fixable by adding '#include <cassert>'
  +++ |+#include <cassert>
    1 | 
a.cc:22:14: error: 'begin' was not declared in this scope
   22 |         sort(begin(order), end(order), [&](int a, int b) {
      |              ^~~~~
a.cc:22:28: error: 'end' was not declared in this scope
   22 |         sort(begin(order), end(order), [&](int a, int b) {
      |                            ^~~
a.cc: In lambda function:
a.cc:24:26: error: 'bblock' was not declared in this scope; did you mean 'ablock'?
   24 |             if(ablock != bblock) return ablock < bblock;
      |                          ^~~~~~
      |                          ablock
a.cc:25:35: error: 'right' was not declared in this scope
   25 |             if(ablock & 1) return right[a] < right[b];
      |                                   ^~~~~
a.cc:26:20: error: 'right' was not declared in this scope
   26 |             return right[a] > right[b];
      |                    ^~~~~
a.cc: In member function 'int Mo::run(const int&, const int&, const int&)':
a.cc:22:9: error: 'sort' was not declared in this scope; did you mean 'short'?
   22 |         sort(begin(order), end(order), [&](int a, int b) {
      |         ^~~~
      |         short
a.cc: In lambda function:
a.cc:30:13: error: 'v' was not declared in this scope
   30 |             v[idx].flip();
      |             ^
a.cc:31:27: error: expression cannot be used as a function
   31 |             if(v[idx]) add(idx);
      |                        ~~~^~~~~
a.cc:32:21: error: expression cannot be used as a function
   32 |             else del(idx);
      |                  ~~~^~~~~
a.cc: In member function 'int Mo::run(const int&, const int&, const int&)':
a.cc:36:24: error: 'right' was not declared in this scope
   36 |             while(nr < right[idx]) push(nr++);
      |                        ^~~~~
a.cc:38:24: error: 'right' was not declared in this scope
   38 |             while(nr > right[idx]) push(--nr);
      |                        ^~~~~
a.cc:39:16: error: expression cannot be used as a function
   39 |             rem(idx);
      |             ~~~^~~~~
a.cc:41:5: warning: no return statement in function returning non-void [-Wreturn-type]
   41 |     }
      |     ^
a.cc: In function 'int main()':
a.cc:46:5: error: 'cin' was not declared in this scope
   46 |     cin >> N;
      |     ^~~
a.cc:49:5: error: 'vector' was not declared in this scope
   49 |     vector< int > A(N);
      |     ^~~~~~
a.cc:49:13: error: expected primary-expression before 'int'
   49 |     vector< int > A(N);
      |             ^~~
a.cc:51:16: error: 'A' was not declared in this scope
   51 |         cin >> A[i];
      |                ^
a.cc:53:13: error: expected primary-expression before 'int'
   53 |     vector< int > f(1000001);
      |             ^~~
a.cc: In lambda function:
a.cc:62:34: error: 'f' was not declared in this scope
   62 |     auto add = [&](int idx) { if(f[A[idx]]++ == 0) ret++; };
      |                                  ^
a.cc:62:36: error: 'A' was not declared in this scope
   62 |     auto add = [&](int idx) { if(f[A[idx]]++ == 0) ret++; };
      |                                    ^
a.cc: In lambda function:
a.cc:63:34: error: 'f' was not declared in this scope
   63 |     auto del = [&](int idx) { if(f[A[idx]]-- == 1) --ret; };
      |                                  ^
a.cc:63:36: error: 'A' was not declared in this scope
   63 |     auto del = [&](int idx) { if(f[A[idx]]-- == 1) --ret; };
      |                                    ^
a.cc: In function 'int main()':
a.cc:64:13: error: expected primary-expression before 'int'
   64 |     vector< int > ans(Q);
      |             ^~~
a.cc: In lambda function:
a.cc:65:31: error: 'ans' was not declared in this scope
   65 |     auto rem = [&](int idx) { ans[idx] = ret; };
      |                               ^~~
a.cc: In function 'int main()':
a.cc:66:12: error: cannot convert 'main()::<lambda(int)>' to 'const int&'
   66 |     mo.run(add, del, rem);
      |            ^~~
      |            |
      |            main()::<lambda(int)>
a.cc:20:24: note:   initializing argument 1 of 'int Mo::run(const int&, const int&, const int&)'
   20 |     int run(const ADD &add, const DEL &del, const REM &rem) {
      |             ~~~~~~~~~~~^~~
a.cc:68:9: error: 'cout' was not declared in this scope
   68 |         cout << ans[i] << "\n";
      |         ^~~~
a.cc:68:17: error: 'ans' was not declared in this scope
   68 |         cout << ans[i] << "\n";
      |                 ^~~