# SP3267 D-query

## 思路

while(r < qr) add(++r);
while(r > qr) del(r--);
while(l < ql) del(l++);


const int part = sqrt(n) + 1;
sort(querry.begin() , querry.end() , [&](auto &A , auto &B){
if(A.l / part == B.l / part) return A.r < B.r;
return A.l / part < B.l / part;
}) ;


#include <algorithm>
#include <iostream>
#include <tuple>
#include <vector>

using namespace std;

int main() {
ios::sync_with_stdio(false);
cin.tie(0);

int maxx = -1;
int n;
cin >> n;
vector<int> v(n);
for (auto &x : v) {
cin >> x;
x--;
maxx = max(maxx, x);
}
vector<int> cnt(maxx + 1, 0);

int q;
cin >> q;

vector<tuple<int, int, int>> querry(q);

auto get_mid = [](int x) -> int {
int l = 0, r = 1e4;
int res = -1;
while (l <= r) {
int m = (l + r) >> 1;
if (m * m >= x) {
res = m;
r = m - 1;
} else {
l = m + 1;
}
}
return res;
};

const int prt = get_mid(n);

for (int i = 0; i < q; i++) {
auto &[l, r, id] = querry[i];
cin >> l >> r;
l--, r--;
id = i;
}

sort(querry.begin(), querry.end(), [&](auto &A, auto &B) {
auto [la, ra, ida] = A;
auto [lb, rb, idb] = B;
if (la / prt == lb / prt) return ra < rb;
return la / prt < lb / prt;
});

vector<int> ans(q);

int l = 0, r = -1;

int res = 0;

auto add = [&](int idex) -> void {
if (cnt[v[idex]] == 0) res++;
cnt[v[idex]]++;
};

auto mov = [&](int idex) -> void {
cnt[v[idex]]--;
if (cnt[v[idex]] == 0) res--;
};

for (auto [ql, qr, id] : querry) {
while (l < ql) mov(l++);
while (r > qr) mov(r--);
ans[id] = res;
}

for (auto &x : ans) cout << x << '\n';

return 0;
}


#include <algorithm>
#include <iostream>
#include <tuple>
#include <vector>

using namespace std;

struct SEG_Tree {
vector<pair<int, int>> Range;
vector<int> cnt;
SEG_Tree(int n) {
int size = 1;
while (size < n) size *= 2;
Range.assign(size * 2, {});
cnt.assign(size * 2, {});
build(0, n - 1);
}

int Lson(int x) { return x * 2 + 1; }
int Rson(int x) { return x * 2 + 2; }

void build(int l, int r, int p = 0) {
Range[p] = {l, r};
if (l == r) return;
int m = (l + r) >> 1;
build(l, m, Lson(p));
build(m + 1, r, Rson(p));
push_up(p);
}

void push_up(int p) { cnt[p] = cnt[Lson(p)] + cnt[Rson(p)]; }

void add(int x, int val, int p = 0) {
auto [l, r] = Range[p];
if (l == x && r == x) {
cnt[p] = val;
return;
}
int m = (l + r) >> 1;
if (x <= m) add(x, val, Lson(p));
if (x > m) add(x, val, Rson(p));
push_up(p);
}

int sum(int x, int y, int p = 0) {
auto [l, r] = Range[p];
if (x <= l && r <= y) {
return cnt[p];
}
int m = (l + r) >> 1;
int res = 0;
if (x <= m) res += sum(x, y, Lson(p));
if (y > m) res += sum(x, y, Rson(p));
return res;
}
};

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
vector<int> v(n);
const int N = 1e6 + 10;
vector<int> pos(N, -1);
for (auto &x : v) cin >> x;
int q;
cin >> q;

vector<int> ans(q);
vector<tuple<int, int, int>> que(q);

int now = 0;

for (auto &[r, l, id] : que) {
id = now++;
cin >> l >> r;
l--, r--;
}

sort(que.begin(), que.end());

now = 0;

SEG_Tree st(n);
for (auto [r, l, id] : que) {
while (now < v.size() && now <= r) {
if (pos[v[now]] != -1) st.add(pos[v[now]], 0);