Language: C++

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
int i;
#define rep2(i, a, b) for(i = a; i <= b; ++i)
#define rep(i, n) for(i = 0; i < n; ++i)
using namespace std;
// _________コーディングはここから！！___________
template <const int sz = 5 * 10000000, typename T = long long> struct IO {
    char reader[sz], writer[sz];
    char *now, *now2 = writer;
    IO() {
        reader[fread(reader, sizeof(char), sizeof(char) * sz, stdin)];
        now = reader;
    }
    inline T read() {
        while(*now && *now <= 32) now++;
        if(*now == '-') {
            now++;
            T res = 0;
            while('0' <= *now and *now <= '9') { res = res * 10 + *now++ - '0'; }
            return -res;
        } else {
            T res = 0;
            while('0' <= *now and *now <= '9') { res = res * 10 + *now++ - '0'; }
            return res;
        }
    }
    inline string read_str() {
        string res;
        while(*now and *now != '\n' and *now != ' ') res += *now++;
        now++;
        return res;
    }
    inline void write(T x, char margin = ' ') {
        if(x == 0) {
            putchar('0');
            putchar(margin);
            return;
        }
        if(x < 0) {
            putchar('-');
            x = -x;
        }
        while(x) {
            *now2 = '0' + x % 10;
            now2++;
            x /= 10;
        }
        do {
            now2--;
            putchar(*now2);
        } while(now2 != writer);
        putchar(margin);
    }
    inline void write_str(string s, char margin = ' ') {
        for(auto c : s) putchar(c);
        putchar(margin);
    }
};
IO io;
inline int read() { return io.read(); }
inline void write(int x) { io.write(x); }
inline void write(int x, char c) { io.write(x, c); }
constexpr int N = 500003;
int c[N];
struct T {
    int l, r, idx;
    constexpr bool operator<(const T &rhs) const noexcept { return r < rhs.r; }
} q[N];
int ans[N], last[N], dat[N];

/**
 * Fenwick Tree(0-indexed, int only)
 * X is height of tree
 * yosupo さん
 */

template <int X> struct FenwickSimd {
    int *seg_base;
    int *(seg[X]);
    m256 segC;
    FenwickSimd() {}
    FenwickSimd(int N) {
        // N < 8**X
        assert(N < 1 << (3 * X));
        int S = 0;
        int segCbuf[8] = {};
        for(int i = 0; i < X; i++) {
            N = (N + 7) / 8;
            segCbuf[i] = S;
            S += 8 * (N + 1);
        }
        seg_base = (int *)aligned_alloc(32, sizeof(int) * S);
        for(int i = 0; i < X; i++) { seg[i] = seg_base + segCbuf[i]; }
        segC = _mm256_load_si256((m256 *)segCbuf);
    }
    /// a[i] += x
    void add(int p, int x) {
        for(int i = 0; i < X; i++) {
            int dp = p & 7, up = p & ~7;

            const m256 pd = _mm256_set1_epi32(dp);
            const m256 base = _mm256_set_epi32(7, 6, 5, 4, 3, 2, 1, 0);
            m256 xx = _mm256_set1_epi32(x);
            xx = _mm256_and_si256(xx, _mm256_cmpgt_epi32(base, pd));

            m256 tar = _mm256_load_si256((m256 *)(seg[i] + up));
            tar = _mm256_add_epi32(tar, xx);
            _mm256_store_si256((m256 *)(seg[i] + up), tar);

            p >>= 3;
        }
    }
    // sum [0, i)
    int sum(int p) {
        int s{0};
        const m256 off = _mm256_set_epi32(21, 18, 15, 12, 9, 6, 3, 0);
        m256 adr = _mm256_set1_epi32(p);
        adr = _mm256_srlv_epi32(adr, off);
        adr = _mm256_add_epi32(adr, segC);

        m256 buf = _mm256_setzero_si256();
        const m256 mask =
            _mm256_set_epi32(7 < X ? -1 : 0, 6 < X ? -1 : 0, 5 < X ? -1 : 0, 4 < X ? -1 : 0, 3 < X ? -1 : 0, 2 < X ? -1 : 0, 1 < X ? -1 : 0, 0 < X ? -1 : 0);
        buf = _mm256_mask_i32gather_epi32(buf, seg_base, adr, mask, 4);

        buf = _mm256_hadd_epi32(buf, buf);
        buf = _mm256_hadd_epi32(buf, buf);
        s += _mm256_extract_epi32(buf, 0);
        s += _mm256_extract_epi32(buf, 4);

        return s;
    }
    // sum [a, b)
    inline int sum(int a, int b) { return sum(b) - sum(a); }
};
int n, Q, now = 1;

// 頑張れ！！
#pragma GCC target("avx2")
#pragma GCC optimize("unroll-loops")
// 頑張れ！！

main() {
    n = read(), Q = read();
    rep2(i, 1, n) c[i] = read();
    rep(i, Q) q[i].l = read(), q[i].r = read() + 1, q[i].idx = i;
    sort(q, q + Q);
    FenwickSimd<N> bit(N);
    rep(i, Q) {
        for(; now < q[i].r; ++now) {
            if(last[c[now]]) bit.add(last[c[now]]);
            last[c[now]] = now;
        }
        ans[q[i].idx] = bit.sum(q[i].r - 1) - bit.sum(q[i].l - 1) + q[i].r - q[i].l;
    }
    rep(i, Q) write(ans[i], '\n');
}


Compiler output:
a.cc:81:5: error: 'm256' does not name a type
   81 |     m256 segC;
      |     ^~~~
a.cc: In constructor 'FenwickSimd<X>::FenwickSimd(int)':
a.cc:95:9: error: 'segC' was not declared in this scope; did you mean 'seg'?
   95 |         segC = _mm256_load_si256((m256 *)segCbuf);
      |         ^~~~
      |         seg
a.cc:95:35: error: 'm256' was not declared in this scope
   95 |         segC = _mm256_load_si256((m256 *)segCbuf);
      |                                   ^~~~
a.cc:95:41: error: expected primary-expression before ')' token
   95 |         segC = _mm256_load_si256((m256 *)segCbuf);
      |                                         ^
a.cc:95:16: error: there are no arguments to '_mm256_load_si256' that depend on a template parameter, so a declaration of '_mm256_load_si256' must be available [-fpermissive]
   95 |         segC = _mm256_load_si256((m256 *)segCbuf);
      |                ^~~~~~~~~~~~~~~~~
a.cc:95:16: note: (if you use '-fpermissive', G++ will accept your code, but allowing the use of an undeclared name is deprecated)
a.cc: In member function 'void FenwickSimd<X>::add(int, int)':
a.cc:102:19: error: 'm256' does not name a type
  102 |             const m256 pd = _mm256_set1_epi32(dp);
      |                   ^~~~
a.cc:103:19: error: 'm256' does not name a type
  103 |             const m256 base = _mm256_set_epi32(7, 6, 5, 4, 3, 2, 1, 0);
      |                   ^~~~
a.cc:104:13: error: 'm256' was not declared in this scope
  104 |             m256 xx = _mm256_set1_epi32(x);
      |             ^~~~
a.cc:105:13: error: 'xx' was not declared in this scope; did you mean 'x'?
  105 |             xx = _mm256_and_si256(xx, _mm256_cmpgt_epi32(base, pd));
      |             ^~
      |             x
a.cc:105:58: error: 'base' was not declared in this scope
  105 |             xx = _mm256_and_si256(xx, _mm256_cmpgt_epi32(base, pd));
      |                                                          ^~~~
a.cc:105:64: error: 'pd' was not declared in this scope; did you mean 'dp'?
  105 |             xx = _mm256_and_si256(xx, _mm256_cmpgt_epi32(base, pd));
      |                                                                ^~
      |                                                                dp
a.cc:105:39: error: there are no arguments to '_mm256_cmpgt_epi32' that depend on a template parameter, so a declaration of '_mm256_cmpgt_epi32' must be available [-fpermissive]
  105 |             xx = _mm256_and_si256(xx, _mm256_cmpgt_epi32(base, pd));
      |                                       ^~~~~~~~~~~~~~~~~~
a.cc:107:18: error: expected ';' before 'tar'
  107 |             m256 tar = _mm256_load_si256((m256 *)(seg[i] + up));
      |                  ^~~
a.cc:108:13: error: 'tar' was not declared in this scope; did you mean 'tan'?
  108 |             tar = _mm256_add_epi32(tar, xx);
      |             ^~~
      |             tan
a.cc:108:19: error: there are no arguments to '_mm256_add_epi32' that depend on a template parameter, so a declaration of '_mm256_add_epi32' must be available [-fpermissive]
  108 |             tar = _mm256_add_epi32(tar, xx);
      |                   ^~~~~~~~~~~~~~~~
a.cc:109:39: error: expected primary-expression before ')' token
  109 |             _mm256_store_si256((m256 *)(seg[i] + up), tar);
      |                                       ^
a.cc:109:13: error: there are no arguments to '_mm256_store_si256' that depend on a template parameter, so a declaration of '_mm256_store_si256' must be available [-fpermissive]
  109 |             _mm256_store_si256((m256 *)(seg[i] + up), tar);
      |             ^~~~~~~~~~~~~~~~~~
a.cc: In member function 'int FenwickSimd<X>::sum(int)':
a.cc:117:15: error: 'm256' does not name a type
  117 |         const m256 off = _mm256_set_epi32(21, 18, 15, 12, 9, 6, 3, 0);
      |               ^~~~
a.cc:118:9: error: 'm256' was not declared in this scope
  118 |         m256 adr = _mm256_set1_epi32(p);
      |         ^~~~
a.cc:119:9: error: 'adr' was not declared in this scope; did you mean 'add'?
  119 |         adr = _mm256_srlv_epi32(adr, off);
      |         ^~~
      |         add
a.cc:119:38: error: 'off' was not declared in this scope
  119 |         adr = _mm256_srlv_epi32(adr, off);
      |                                      ^~~
a.cc:119:15: error: there are no arguments to '_mm256_srlv_epi32' that depend on a template parameter, so a declaration of '_mm256_srlv_epi32' must be available [-fpermissive]
  119 |         adr = _mm256_srlv_epi32(adr, off);
      |               ^~~~~~~~~~~~~~~~~
a.cc:120:37: error: 'segC' was not declared in this scope; did you mean 'seg'?
  120 |         adr = _mm256_add_epi32(adr, segC);
      |                                     ^~~~
      |                                     seg
a.cc:120:15: error: there are no arguments to '_mm256_add_epi32' that depend on a template parameter, so a declaration of '_mm256_add_epi32' must be available [-fpermissive]
  120 |         adr = _mm256_add_epi32(adr, segC);
      |               ^~~~~~~~~~~~~~~~
a.cc:122:14: error: expected ';' before 'buf'
  122 |         m256 buf = _mm256_setzero_si256();
      |              ^~~
a.cc:123:15: error: 'm256' does not name a type
  123 |         const m256 mask =
      |               ^~~~
a.cc:125:9: error: 'buf' was not declared in this scope
  125 |         buf = _mm256_mask_i32gather_epi32(buf, seg_base, adr, mask, 4);
      |         ^~~
a.cc:125:63: error: 'mask' was not declared in this scope; did you mean 'std::filesystem::perms::mask'?
  125 |         buf = _mm256_mask_i32gather_epi32(buf, seg_base, adr, mask, 4);
      |                                                               ^~~~
      |                                                               std::filesystem::perms::mask
In file included from /usr/include/c++/14/filesystem:51,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:200,
                 from a.cc:2:
/usr/include/c++/14/bits/fs_fwd.h:162:7: note: 'std::filesystem::perms::mask' declared here
  162 |       mask              = 07777,
      |       ^~~~
a.cc:125:15: error: there are no arguments to '_mm256_mask_i32gather_epi32' that depend on a template parameter, so a declaration of '_mm256_mask_i32gather_epi32' must be available [-fpermissive]
  125 |         buf = _mm256_mask_i32gather_epi32(buf, seg_base, adr, mask, 4);
      |               ^~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:127:15: error: there are no arguments to '_mm256_hadd_epi32' that depend on a template parameter, so a declaration of '_mm256_hadd_epi32' must be available [-fpermissive]
  127 |         buf = _mm256_hadd_epi32(buf, buf);
      |               ^~~~~~~~~~~~~~~~~
a.cc:128:15: error: there are no arguments to '_mm256_hadd_epi32' that depend on a template parameter, so a declaration of '_mm256_hadd_epi32' must be available [-fpermissive]
  128 |         buf = _mm256_hadd_epi32(buf, buf);
      |               ^~~~~~~~~~~~~~~~~
a.cc:129:14: error: there are no arguments to '_mm256_extract_epi32' that depend on a template parameter, so a declaration of '_mm256_extract_epi32' must be available [-fpermissive]
  129 |         s += _mm256_extract_epi32(buf, 0);
      |              ^~~~~~~~~~~~~~~~~~~~
a.cc:130:14: error: there are no arguments to '_mm256_extract_epi32' that depend on a template parameter, so a declaration of '_mm256_extract_epi32' must be available [-fpermissive]
  130 |         s += _mm256_extract_epi32(buf, 4);
      |              ^~~~~~~~~~~~~~~~~~~~
a.cc: At global scope:
a.cc:144:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  144 | main() {
      | ^~~~
a.cc: In function 'int main()':
a.cc:152:37: error: no matching function for call to 'FenwickSimd<500003>::add(int&)'
  152 |             if(last[c[now]]) bit.add(last[c[now]]);
      |                              ~~~~~~~^~~~~~~~~~~~~~
a.cc:98:10: note: candidate: 'void FenwickSimd<X>::add(int, int) [with int X = 500003]'
   98 |     void add(int p, int x) {
      |          ^~~
a.cc:98:10: note:   candidate expects 2 arguments, 1 provided
In file included from /usr/include/c++/14/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:106:
a.cc: In instantiation of 'FenwickSimd<X>::FenwickSimd(int) [with int X = 500003]':
a.cc:149:25:   required from here
  149 |     FenwickSimd<N> bit(N);
      |                         ^
a.cc:85:22: warning: left shift count >= width of type [-Wshift-count-overflow]
   85 |         assert(N < 1 << (3 * X));
      |                    ~~^~~~~~~~~~
a.cc: In instantiation of 'int FenwickSimd<X>::sum(int) [with int X = 500003]':
a.cc:155:32:   required from here
  155 |         ans[q[i].idx] = bit.sum(q[i].r - 1) - bit.sum(q[i].l - 1) + q[i].r - q[i].l;
      |                         ~~~~~~~^~~~~~~~~~~~
a.cc:120:41: error: '_mm256_add_epi32' was not declared in this scope
  120 |         adr = _mm256_add_epi32(adr, segC);
      |                                         ^
a.cc:127:32: error: '_mm256_hadd_epi32' was not declared in this scope
  127 |         buf = _mm256_hadd_epi32(buf, buf);
      |               ~~~~~~~~~~~~~~~~~^~~~~~~~~~
a.cc:128:32: error: '_mm256_hadd_epi32' was not declared in this scope, and no declarations were found by argument-dependent lookup at the point of instantiation
  128 |         buf = _mm256_hadd_epi32(buf, buf);
      |               ~~~~~~~~~~~~~~~~~^~~~~~~~~~
a.cc:127:32: note: '_mm256_hadd_epi32' declared here, later in the translation unit
  127 |         buf = _mm256_hadd_epi32(buf, buf);
      |               ~~~~~~~~~~~~~~~~~^~~~~~~~~~
a.cc:129:34: error: '_mm256_extract_epi32' was not declared in this scope
  129 |         s += _mm256_extract_epi32(buf, 0);
      |              ~~~~~~~~~~~~~~~~~~~~^~~~~~~~
a.cc:130:34: error: '_mm256_extract_epi32' was not declared in this scope, and no declarations were found by argument-dependent lookup at the point of instantiation
  130 |         s += _mm256_extract_epi32(buf, 4);
      |              ~~~~~~~~~~~~~~~~~~~~^~~~~~~~
a.cc:129:34: note: '_mm256_extract_epi32' declared here, later in the translation unit
  129 |         s += _mm256_extract_epi32(buf, 0);
      |