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 さん
 */
#include <immintrin.h>
template <int X> struct FenwickSimd {
#define m256 __m256i
    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)
    int sum(int a, int b) { return sum(b) - sum(a); }
};
int n, Q, now = 1;

// 頑張れ！！
#pragma GCC target("avx,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]], 1);
            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:145:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  145 | main() {
      | ^~~~
In file included from /usr/include/c++/14/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:106,
                 from a.cc:2:
a.cc: In instantiation of 'FenwickSimd<X>::FenwickSimd(int) [with int X = 500003]':
a.cc:150:25:   required from here
  150 |     FenwickSimd<N> bit(N);
      |                         ^
a.cc:86:22: warning: left shift count >= width of type [-Wshift-count-overflow]
   86 |         assert(N < 1 << (3 * X));
      |                    ~~^~~~~~~~~~
a.cc: In constructor 'FenwickSimd<X>::FenwickSimd(int) [with int X = 500003]':
a.cc:96:14: warning: AVX vector return without AVX enabled changes the ABI [-Wpsabi]
   96 |         segC = _mm256_load_si256((m256 *)segCbuf);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/lib/gcc/x86_64-linux-gnu/14/include/immintrin.h:43,
                 from a.cc:77:
/usr/lib/gcc/x86_64-linux-gnu/14/include/avxintrin.h:915:1: error: inlining failed in call to 'always_inline' '__m256i _mm256_load_si256(const __m256i*)': target specific option mismatch
  915 | _mm256_load_si256 (__m256i const *__P)
      | ^~~~~~~~~~~~~~~~~
a.cc:96:33: note: called from here
   96 |         segC = _mm256_load_si256((m256 *)segCbuf);
      |                ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~