传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1878
以每个询问左端点所属的块的编号为第一关键字，右端点本身为第二关键字，排序，然后保利扫描，先移动右指针。
（逻辑相等号写成赋值号，调了1个小时，天呐，上次犯这个错误是多久以前了呀？）
#include <cstdio>
#include <algorithm>
#include <cmath> const int maxn = 50005, maxm = 200005; int n, m, a[maxn], ans[maxm], siz, ima, left, right, book[1000005];
struct query {
int l, r, id;
} b[maxm]; bool cmp(const query & aa, const query & ss) {
if (aa.l / siz == ss.l / siz) {
return aa.r < ss.r;
}
return aa.l / siz < ss.l / siz;
} int main(void) {
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
scanf("%d", &n);
siz = (int)sqrt((float)n + 0.5f);
for (int i = 1; i <= n; ++i) {
scanf("%d", a + i);
}
scanf("%d", &m);
for (int i = 1; i <= m; ++i) {
scanf("%d%d", &b[i].l, &b[i].r);
b[i].id = i;
}
std::sort(b + 1, b + m + 1, cmp); //a[0] = 1000003;
book[a[0]] = 1;
ima = 1;
for (int i = 1; i <= m; ++i) {
while (right < b[i].r) {
++right;
if (++book[a[right]] == 1) {
++ima;
}
}
while (right > b[i].r) {
if (--book[a[right]] == 0) {
--ima;
}
--right;
}
while (left < b[i].l) {
if (--book[a[left]] == 0) {
--ima;
}
++left;
}
while (left > b[i].l) {
--left;
if (++book[a[left]] == 1) {
++ima;
}
}
ans[b[i].id] = ima;
} for (int i = 1; i <= m; ++i) {
printf("%d\n", ans[i]);
}
return 0;
}