题目大意

静态区间查询不同数的个数。

分析

好了，成功被这道题目拉低了AC率。。。

打了莫队T飞掉了，真的是飞掉了QwQ。

蒟蒻想不出主席树的做法，就换成了莫队。。。

---

很多人都不知道莫队是什么。。。

一句话概括莫队：离线询问分块排序，玄学降低复杂度

---

那么这道题目就是简单的莫队模板套一下就好了，每一次看看更新的点是不是会对答案造成贡献就可以过掉了。

但是复杂度很明显是\(Q(\sqrt{n}m)\)，成功T掉，加上玄学卡常，破罐子破摔了100+终于过掉了。

#include 
    
     #define ll long long#define ms(a, b) memset(a, b, sizeof(a))#define inf 0x3f3f3f3f#define N 500005#define M 1000005using namespace std;template 
     
      inline void read(T &x) {    x = 0; T fl = 1; char ch = 0;    for (; ch < '0' || ch > '9'; ch = getchar())        if (ch == '-') fl = -1;    for (; ch >= '0' && ch <= '9'; ch = getchar())        x = (x << 1) + (x << 3) + (ch ^ 48);    x *= fl;}int buf[1 << 20];template 
      
       inline void write(T x) {    if (x < 0) putchar('-'), x = -x;    if (x > 9) write(x / 10);    putchar(x % 10 + '0');}struct node {    int l, r, bl, id;    bool operator <(const node &rhs) const {        return (bl == rhs.bl)? ((bl & 1)? (r < rhs.r): (r > rhs.r)): (bl < rhs.bl);    }}q[N];int block, res = 0, n, m;int clo[M], a[N], ans[N];inline void update(register int x, register int opt) {    clo[a[x]] += opt;    if (opt == -1) if (clo[a[x]] == 0) res += opt;    if (opt == 1) if (clo[a[x]] == 1) res += opt;}int main() {    read(n); block = sqrt(n);    for (register int i = 1; i <= n; ++ i) read(a[i]);    read(m);    for (register int i = 1; i <= m; ++ i) {        read(q[i].l); read(q[i].r);        q[i].bl = (q[i].l + 1) / block;        q[i].id = i;    }    sort(q + 1, q + 1 + m);    register int l = 1, r = 0;    for (register int i = 1; i <= m; ++ i) {        while (r < q[i].r) update(++ r, 1);        while (r > q[i].r) update(r --, -1);        while (l > q[i].l) update(-- l, 1);         while (l < q[i].l) update(l ++, -1);        ans[q[i].id] = res;    }    for (register int i = 1; i <= m; ++ i) write(ans[i]), putchar('\n');    return 0;}