莫队
<pre><code class="language-cpp">#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn = 1010000;
int n, m;
int num[maxn];
namespace moQueue{
const int maxnb = sqrt(maxn) + 1;
struct Query{
int l;
int r;
int id;
Query(int _l = 0, int _r = 0, int _id = 0){
l = _l;
r = _r;
id = _id;
}
};
int cnt[maxn], belong[maxn];
int size, bnum;//一个块大小和块的数量
int now, ans[maxn];
Query q[maxn];
int cmp(Query a, Query b) {
return (belong[a.l] ^ belong[b.l]) ? belong[a.l] < belong[b.l] : ((belong[a.l] & 1) ? a.r < b.r : a.r > b.r);
}
void add(int pos) {
if(!cnt[num[pos]]) ++now;
++cnt[num[pos]];
}
void del(int pos) {
--cnt[num[pos]];
if(!cnt[num[pos]]) --now;
}
void init(){
size = sqrt(n);
bnum = ceil((double)n / size);
for(int i = 1; i <= bnum; ++i){
for(int j = (i - 1) * size + 1; j <= i * size; ++j) {
belong[j] = i;
}
}
}
}
int main() {
scanf("%d", &n);
for(int i = 1; i <= n; ++i) scanf("%d", &num[i]);
scanf("%d", &m);
for(int i = 1; i <= m; ++i) {
scanf("%d%d", &moQueue::q[i].l, &moQueue::q[i].r);
moQueue::q[i].id = i;
}
sort(moQueue::q + 1, moQueue::q + m + 1, moQueue::cmp);
int l = 1, r = 0;
for(int i = 1; i <= m; ++i) {
int ql = moQueue::q[i].l, qr = moQueue::q[i].r;
while(l < ql) moQueue::del(l++);
while(l > ql) moQueue::add(--l);
while(r < qr) moQueue::add(++r);
while(r > qr) moQueue::del(r--);
moQueue::ans[moQueue::q[i].id] = moQueue::now;
}
for(int i = 1; i <= m; ++i) printf("%d ", moQueue::ans[i]);
return 0;
}</code></pre>