本题强制离线？

#include <iostream>
#include <algorithm>

constexpr int maxv = 1000005, maxn = 500005;

struct Node {
    int val = 0;
    Node *lson = nullptr, *rson = nullptr;
} pool[maxn * 20 + 3], *addr[maxn];

int ptr = 0, n, m, prev[maxv];

Node* alloc() {
    return pool + ++ptr;
}

void update(Node *rt) {
    rt->val = 0;
    if (rt->lson) rt->val += rt->lson->val;
    if (rt->rson) rt->val += rt->rson->val;
}

#define MID (((l) + (r)) >> 1)

void modify(int l, int r, Node *rt, Node *prev, int v) {
    // std::cout << l << '-' << r << std::endl;
    if (l == r) {
        rt->val = prev->val + 1;
        // std::cout << "--- " << rt->val << std::endl;
        return;
    }
    if (v <= MID) {
        rt->rson = prev->rson;
        modify(l, MID, rt->lson = alloc(), prev->lson, v);
    } else {
        rt->lson = prev->lson;
        modify(MID + 1, r, rt->rson = alloc(), prev->rson, v);
    }
    update(rt);
}

int query(int l, int r, Node *rt, int p) {
    if (!rt) return 0;
    if (r <= p) return rt->val;
    int res = query(l, MID, rt->lson, p);
    if (p > MID) res += query(MID + 1, r, rt->rson, p);
    return res;
}

int main() {
    pool->lson = pool->rson = addr[0] = pool;
    std::cin >> n;
    for (int i = 1; i <= n; ++i) {
        int temp = 0;
        std::cin >> temp;
        modify(0, maxn, addr[i] = alloc(), addr[i - 1], prev[temp]);
        prev[temp] = i;
    }
    std::cin >> m;
    while (m--) {
        int x, y, a, b;
        std::cin >> x >> y, b = query(0, maxn, addr[x - 1], x - 1);
        a = query(0, maxn, addr[y], x - 1);
        // std::cout << a << '=' << b << std::endl;
        std::cout << a - b << std::endl;
    }
    return 0;
}