06. Xor sum

07. Pass!

09. KD-Graph

10. zoto

题意：给出一个序列，离线查询m个区间$[l_i,r_i]$中，在数值区间$[d_i,u_i]$中有多少个不同的数，n=1e5

首先考虑在数值区间上维护问题，也就是维护一个支持单点修改和区间查询的数据结构，很容易想到用线段树之类的方法实现$O(\log n)$的修改和查询

离线查询若干个区间，可以再想到莫队算法，每次修改复杂度$O(\sqrt n)$，查询$O(1)$，将上述两种结构合并后发现，修改复杂度达到了$O(\sqrt n\log n)$，显然超时

于是为了使总复杂度限制在$O(n\sqrt n)$，需要在数值区间上维护一个$O(1)$修改，$O(\sqrt n)$查询的做法，这个方法就是分块，维护$num[i]$记录数i出现的次数，$sum[i]$记录第i个块中不同数的个数，两者合并起来刚好是$O(n\sqrt n)$

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> pii;

const int N = 1e5 + 5;

int T, n, m, a[N], block[N], bs, ans[N], sq, num[N], sum[N];

int block2[N], sq2;

struct Query {
    int l, r, d, u, idx;
    bool operator < (Query &Q) const {
        if (block[l] != block[Q.l])
            return l < Q.l;
        else return r < Q.r;
    }
}q[N];

void modify(int pos, int type) {
    int x = a[pos];
    if (type == 1) {
        num[x]++;
        if (num[x] == 1) sum[block2[x]]++;
    } else {
        num[x]--;
        if (num[x] == 0) sum[block2[x]]--;
    }
}

int Ask(int l, int r) {
    int res = 0;
    if (block2[l] == block2[r]) {
        for (int i = l; i <= r; i++) res += (num[i] > 0);
        return res;
    }
    for (int i = block2[l] + 1; i <= block2[r] - 1; i++) {
        res += sum[i];
    }
    for (int i = l; i <= sq2 * block2[l]; i++) res += (num[i] > 0);
    for (int i = sq2 * (block2[r] - 1) + 1; i <= r; i++) res += (num[i] > 0);
    return res;
}

int main() {
    scanf("%d", &T);
    sq2 = (int)sqrt(N);
    for (int i = 0; i <= 100000; i++) block2[i] = i <= sq2 ? 1 : block2[i - sq2] + 1;
    while(T--) {
        memset(num, 0, sizeof(num));
        memset(sum, 0, sizeof(sum));
        scanf("%d %d", &n, &m);
        for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
        int sq = (int)sqrt(n);
        for (int i = 1; i <= n; i++) block[i] = i <= sq ? 1 : block[i - sq] + 1;
        for (int i = 1; i <= m; i++) {
            int x[2], y[2]; scanf("%d %d %d %d", &x[0], &y[0], &x[1], &y[1]);
            q[i] = {x[0], x[1], y[0], y[1], i};
        }
        sort(q + 1, q + 1 + m);
        int L, R;
        L = 1, R = 0;
        for (int i = 1; i <= m; i++) {
            while(R < q[i].r) modify(++R, 1);
            while(L > q[i].l) modify(--L, 1);
            while(R > q[i].r) modify(R--, -1);
            while(L < q[i].l) modify(L++, -1);
            ans[q[i].idx] = Ask(q[i].d, q[i].u);
        }
        for (int i = 1; i <= m; i++) {
            printf("%d\n", ans[i]);
        }
    }
    return 0;
}