满足无区间修改，可离线，可$O(1)$得到相邻区间的计数，即可$O(qlogq+n^{\frac{3}{2}})$求出q个查询$[l,r],1≤l≤r≤n$

算法流程

将长度为n的区间分成约$\sqrt n$个块，每块的大小最多为$\lfloor\sqrt n\rfloor$。确定每个查询的左端点所属块号，若第i个查询为$[l_i,r_i]$，$l_i$确定的块号$\frac{l_i}{\lfloor\sqrt n\rfloor}$

将q个查询进行排序，若左端点所属块号相同，则按照右端点升序排序；否则按照左端点所属块号升序排序。

初始双指针$l=1,r=0$。查询排序后，对于第i次查询$[l_i,r_i]$，将$l$移动到$l_i$,将$r$移动到$r_i$。此过程中维护区间计数。注意不能出现$l>r$的情况，所以代码实现中移动判断的顺序有讲究。

双指针移动的时间复杂度为$O(n \sqrt n)$

我们分别考虑左右指针的移动次数。

对于右指针，在区间左端点所属同一块的区间右端点移动时间复杂度为$O(n)$，共$O(\sqrt n)$分块，总时间复杂度为$O(n\sqrt n)$

若分块共计分成sz块，区间左端点分配到第i块的个数为$a_i$，对于第i块中的左端点由于是无序的，我们考虑最坏的移动情况，就是每次移动需要跨越整个块，这时候所需的时间复杂度为$O(a_i\sqrt n)$。所有块所需时间复杂度$O(\sum \limits_{i=1}^{sz} a_i \sqrt n) = O(n \sqrt n)$

q次区间查询，每次查询求区间内去重后的元素个数。

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define N 1000006
#define MOD 998244353
using namespace std;

int bsz;
int cnt[N], v[N], ans[N];
int cur = 0;
struct Node {
    int l, r, id;
    bool operator<(Node& o) {
        return l / bsz == o.l / bsz ? r < o.r : l / bsz < o.l / bsz;
    }
} a[N];

void add(int x) {
    if (++cnt[v[x]] == 1)
        cur++;
}

void sub(int x) {
    if (--cnt[v[x]] == 0)
        cur--;
}

void sol() {
    int n, q;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> v[i];
    }
    cin >> q;
    for (int i = 0; i < q; i++) {
        cin >> a[i].l >> a[i].r;
        a[i].id = i;
    }
    bsz = sqrt(n);
    sort(a, a + q);
    int l = 1, r = 0;
    for (int i = 0; i < q; i++) {
        while (a[i].l < l)
            add(--l);
        while (a[i].r > r)
            add(++r);
        while (a[i].l > l)
            sub(l++);
        while (a[i].r < r)
            sub(r--);
        ans[a[i].id] = cur;
    }
    for (int i = 0; i < q; i++) {
        cout << ans[i] << "\\n";
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}

区间最大频次

int bsz;
int feq[N], cnt[N], v[N], ans[N];
int mxf = 0;
struct Node {
    int l, r, id;
    bool operator<(Node& o) {
        return l / bsz == o.l / bsz ? r < o.r : l / bsz < o.l / bsz;
    }
} a[N];

void add(int x) {
    cnt[feq[v[x]]]--;
    feq[v[x]]++;
    cnt[feq[v[x]]]++;
    mxf = max(mxf, feq[v[x]]);
}

void sub(int x) {
    cnt[feq[v[x]]]--;
    feq[v[x]]--;
    cnt[feq[v[x]]]++;
    if (mxf == feq[v[x]] + 1 && cnt[feq[v[x]] + 1] == 0)
        mxf = feq[v[x]];
}

void sol() {
    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> v[i];
    }
    for (int i = 0; i < q; i++) {
        cin >> a[i].l >> a[i].r;
        a[i].id = i;
    }
    bsz = sqrt(n);
    sort(a, a + q);
    int l = 1, r = 0;
    for (int i = 0; i < q; i++) {
        while (a[i].l < l)
            add(--l);
        while (a[i].r > r)
            add(++r);
        while (a[i].l > l)
            sub(l++);
        while (a[i].r < r)
            sub(r--);
        ans[a[i].id] = mxf;
    }
    for (int i = 0; i < q; i++) {
        cout << ans[i] << "\\n";
    }
}