DQUERY - D-query
Tác giả: happyboy99x
Ngôn ngữ: C++
#include<cstdio>
#include<algorithm>
#include<functional>
using namespace std;
const int N = 30007, Q = 200007, MAX = 1000007;
int n, q, ans[Q], last[MAX], bit[N];
struct query {
int u, v, id;
bool operator < (const query &q) const {
return u < q.u;
}
} qry[Q];
pair<int, int> a[N];
void enter() {
scanf("%d", &n);
for(int i = 1; i <= n; ++i) {
int x; scanf("%d", &x);
a[i] = make_pair(last[x], i);
last[x] = i;
}
scanf("%d", &q);
for(int i = 1; i <= q; ++i) {
scanf("%d%d", &qry[i].u, &qry[i].v);
qry[i].id = i;
}
}
void increase(int v) {
for(; v <= n; v += v & -v) ++bit[v];
}
int sum(int v) {
int res = 0;
for(; v != 0; v -= v & -v) res += bit[v];
return res;
}
void solve() {
sort(qry+1, qry+q+1);
sort(a+1, a+n+1); int p = n;
for(int i = q; i >= 1; --i) {
query &Q = qry[i];
while(a[p].first >= Q.u) increase(a[p--].second);
ans[Q.id] = (Q.v - Q.u + 1) - (sum(Q.v) - sum(Q.u));
}
}
void print() {
for(int i = 1; i <= q; ++i)
printf("%d\n", ans[i]);
}
int main() {
enter();
solve();
print();
return 0;
}