2021杭电多校1 J （普通莫队 树状数组）

题意： 给出1e5个二维平面上的坐标点 0 <= (x, y) <= 1e5, 1e5个询问，每次问x0,y0 到x1,y1的矩阵中有多少y值不同的坐标点。
思路： 操作只有询问，不强制在线，数据范围1e5，就差把莫队的tag标上去了。 莫队离线处理询问区间和区间种类数，求值域内的数用权值线段树或者树状数组解决。
时间复杂度\(ONsqrt(N)log(N)\)
5e8的时间复杂度：

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false) ,cin.tie(0), cout.tie(0);
//#pragma GCC optimize(3,"Ofast","inline")
#define ll long long
#define PII pair<int, int>
//#define int long long
const int N = 1e5 + 5;
const int M = 5e5 + 5;
const int INF = 0x3f3f3f3f;
const ll LNF = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const double PI = acos(-1.0);
int tr[N];
struct Poi { int l, r, id, up, down; } poi[N];
int belong[N], blo;
int a[N], ans[N], cnt[N];
int m, n;
bool st[N];
int lowbit(int x) { return (-x) & x; }
void modify(int x, int val) {
    for (int i = x; i < N; i += lowbit(i)) tr[i] += val;
}
int query(int l, int r) {
    int res = 0;
    for ( int i = r; i; i -= lowbit(i) ) res += tr[i];
    if(l == 1) return res;
    for ( int i = l - 1; i; i -= lowbit(i) ) res -= tr[i];
    return res;
}

int cmp (Poi a, Poi 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[a[pos]]) modify(a[pos], 1); ++cnt[a[pos]]; }
void del(int pos) { --cnt[a[pos]]; if(!cnt[a[pos]]) modify(a[pos], -1); }
void init() {
    memset(st, 0, sizeof st);
    memset(cnt, 0, sizeof cnt);
    memset(tr, 0, sizeof tr);
}
void solve() {
    cin >> n >> m;
    init();
    blo = sqrt(n);
    for ( int i = 1; i <= n; ++ i ) belong[i] = (i - 1) / blo + 1;
    for ( int i = 1; i <= n; ++ i ) cin >> a[i], ++ a[i];
    for ( int i = 1; i <= m; ++ i ) {
        cin >> poi[i].l >> poi[i].down >> poi[i].r >> poi[i].up;
        poi[i].down ++, poi[i].up ++;
        poi[i].id = i;
    }
    sort(poi + 1, poi + m + 1, cmp);
    int l = 1, r = 0;
    for ( int i = 1; i <= m; ++ i ) {
        int ql =poi[i].l,qr=poi[i].r;
        while(l < ql) del(l++);
        while(l > ql) add(--l);
        while(r < qr) add(++r);
        while(r > qr) del(r--);
        ans[poi[i].id] = query(poi[i].down, poi[i].up);
    }

    for(int i=1; i<=m; ++i) cout << ans[i] << "\n";
}
int main() {
    IOS
    int t; cin >> t;
    while(t -- ) solve();
    return 0;
}