bitset 到底有多牛呢？可以轻松草过这个题。

区间数颜色，当然用 bitset 维护每个颜色的出现。合并两个区间只要或起来即可。答案即为 bitset 中 $1$ 的个数。

考虑分治。对于 $[l, r]$，记中点为 $mid$。考虑记录 $[l, mid]$ 的每一个后缀和 $[mid + 1, r]$ 的每一个前缀，查询拼起来即可。

这样直接做要开 $1192 \text{MB}$ 的 bitset，肯定会炸飞。

但是显然我们某一半可以滚掉，对询问排序动态处理即可。这样可以把空间减半。变成 $596 \text{MB}$。

但是这样还是过不去……怎么办？

注意到，只出现一次的数必定会产生贡献，而出现超过 $1$ 次的数至多只有 $\dfrac{n}{2}$ 个，因此我们可以单独处理只出现一次的数，把其他数离散化拿 bitset 存下来。求答案的时候把两部分贡献加起来即可。前者显然可以使用前缀和作差。这样子就只有大概 $298 \text{MB}$，完全可以通过。

分析复杂度。假设 $n, m$ 同阶。看似递归 $\log n$ 层但是推端点是 $O(1)$ 的所以这部分不是瓶颈。bitset 维护 $O(n)$ 个数，询问 $O(n)$ 次，那么复杂度是 $O(\dfrac{n^2}{w})$ 的。跑出来 $0.4 \text{s}$。

#include<bits/stdc++.h>
using namespace std;
bitset<50005> bs[50005], bss;
int n, q, a[100005], pre[100005], ans[100005], buk[100005], mp[100005], idx;
struct que{
    int l, r, id;
}qry[100005];
vector<que> Q[400005], tmp;
vector<int> vec;
void solve(int u, int l, int r){
    if (l == r){
        for (auto v : Q[u])
            ans[v.id] = 1;
        return;
    }
    int mid = (l + r) >> 1;
    tmp.clear();
    for (auto v : Q[u]){
        if (v.r <= mid)
            Q[u << 1].emplace_back(v);
        else if (v.l > mid)
            Q[u << 1 | 1].emplace_back(v);
        else
            tmp.emplace_back(v);
    }
    Q[u].clear();
    for (auto v : tmp)
        Q[u].emplace_back(v);
    sort(Q[u].begin(), Q[u].end(), [](que x, que y){return x.r < y.r;});
    bs[1].reset();
    if (mp[a[mid]] != -1)
        bs[1].set(mp[a[mid]]);
    for (int i = mid - 1; i >= l; i--){
        bs[mid - i + 1] = bs[mid - i];
        if (mp[a[i]] != -1)
            bs[mid - i + 1].set(mp[a[i]]);
    }
    bss.reset();
    auto it = Q[u].begin();
    for (int i = mid + 1; i <= r; i++){
        if (mp[a[i]] != -1)
            bss.set(mp[a[i]]);
        while (it != Q[u].end() && it -> r == i){
            ans[it -> id] = (bss | bs[mid - it -> l + 1]).count() + pre[it -> r] - pre[it -> l - 1];
            ++it;
        }
    }
    solve(u << 1, l, mid);
    solve(u << 1 | 1, mid + 1, r);
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> a[i];
        vec.emplace_back(a[i]);
    }
    cin >> q;
    for (int i = 1; i <= q; i++){
        cin >> qry[i].l >> qry[i].r;
        qry[i].id = i;
        Q[1].emplace_back(qry[i]);
    }
    sort(vec.begin(), vec.end());
    vec.resize(unique(vec.begin(), vec.end()) - vec.begin());
    for (int i = 1; i <= n; i++){
        a[i] = lower_bound(vec.begin(), vec.end(), a[i]) - vec.begin() + 1;
        buk[a[i]]++;
    }
    for (int i = 1; i <= vec.size(); i++){
        if (buk[i] > 1)
            mp[i] = ++idx;
        else
            mp[i] = -1;
    }
    for (int i = 1; i <= n; i++)
        pre[i] = pre[i - 1] + (mp[a[i]] == -1);
    solve(1, 1, n);
    for (int i = 1; i <= q; i++)
        cout << ans[i] << "\n";
    return 0;
}

怎么常数优化呢？可以发现一个小区间内其实数并不是很多，但是 bitset 依然维护 $O(n)$ 个数太搞笑了。手写个 bitset 动态开大小即可有显著优化。跑出来大概 $0.3 \text{s}$。

下面的手写 bitset 是 AI 写的，其他部分由我自己完成。

#include<bits/stdc++.h>
using namespace std;
struct b1tset{
    vector<unsigned long long> b;
    int sz;
    b1tset(int n = 0){
        sz = n;
        b.assign((n + 63) / 64, 0);
    }
    void reset(){
        fill(b.begin(), b.end(), 0ULL);
    }
    void set(int p){
        if (p >= 0 && p < sz)
            b[p >> 6] |= 1ULL << (p & 63);
    }
    int count() const {
        int r = 0;
        for (auto x : b)
            r += __builtin_popcountll(x);
        return r;
    }
    b1tset operator | (const b1tset& o) const {
        b1tset r = *this;
        for (size_t i = 0; i < b.size(); i++)
            r.b[i] |= o.b[i];
        return r;
    }
};
int n, q, a[100005], pre[100005], ans[100005], buk[100005], mp[100005], idx;
struct que{
    int l, r, id;
}qry[100005];
vector<que> Q[400005], tmp;
vector<int> vec;
void solve(int u, int l, int r){
    if (l == r){
        for (auto v : Q[u])
            ans[v.id] = 1;
        return;
    }
    int mid = (l + r) >> 1;
    vec.clear();
    for (int i = l; i <= r; i++){
        vec.emplace_back(a[i]);
        if (l != 1 || r != n)
            buk[a[i]] = 0;
    }
    sort(vec.begin(), vec.end());
    vec.resize(unique(vec.begin(), vec.end()) - vec.begin());
    for (int i = l; i <= r; i++){
        a[i] = lower_bound(vec.begin(), vec.end(), a[i]) - vec.begin() + 1;
        buk[a[i]]++;
    }
    idx = 0;
    for (int i = 1; i <= vec.size(); i++){
        if (buk[i] > 1)
            mp[i] = ++idx;
        else
            mp[i] = -1;
    }
    pre[l - 1] = 0;
    for (int i = l; i <= r; i++)
        pre[i] = pre[i - 1] + (mp[a[i]] == -1);
    b1tset bss(idx + 5);
    vector<b1tset> bs(mid - l + 5, b1tset(idx + 5));
    tmp.clear();
    for (auto v : Q[u]){
        if (v.r <= mid)
            Q[u << 1].emplace_back(v);
        else if (v.l > mid)
            Q[u << 1 | 1].emplace_back(v);
        else
            tmp.emplace_back(v);
    }
    Q[u].clear();
    for (auto v : tmp)
        Q[u].emplace_back(v);
    sort(Q[u].begin(), Q[u].end(), [](que x, que y){return x.r < y.r;});
    bs[1].reset();
    if (mp[a[mid]] != -1)
        bs[1].set(mp[a[mid]]);
    for (int i = mid - 1; i >= l; i--){
        bs[mid - i + 1] = bs[mid - i];
        if (mp[a[i]] != -1)
            bs[mid - i + 1].set(mp[a[i]]);
    }
    bss.reset();
    auto it = Q[u].begin();
    for (int i = mid + 1; i <= r; i++){
        if (mp[a[i]] != -1)
            bss.set(mp[a[i]]);
        while (it != Q[u].end() && it -> r == i){
            ans[it -> id] = (bss | bs[mid - it -> l + 1]).count() + pre[it -> r] - pre[it -> l - 1];
            ++it;
        }
    }
    solve(u << 1, l, mid);
    solve(u << 1 | 1, mid + 1, r);
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    cin >> q;
    for (int i = 1; i <= q; i++){
        cin >> qry[i].l >> qry[i].r;
        qry[i].id = i;
        Q[1].emplace_back(qry[i]);
    }
    solve(1, 1, n);
    for (int i = 1; i <= q; i++)
        cout << ans[i] << "\n";
    return 0;
}