莫队扩展题目：2021杭电多校第一场

给定一个长度为$n$的数组，有$m$次询问，每次询问给出一段区间$[l,r]$，问这段区间值域在$[y_0,y_1]$​中有多少不同的数

本题多组数据，$(1<=T<=5)$

$1<=n<=100000,1<=m<=100000$

每个数$0<=a[i]<=100000$

每次给出的查询范围都是$100000$以内

分析：

（莫队+分块）

用莫队算法的思想，维护询问的区间。对区间中的数按值域进行分块，最后统计答案参考243. 一个简单的整数问题2的思想，段内暴力求解，段间利用分块的sum数组求解

时间复杂度$O(n\sqrt n + m\sqrt n)$

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

const int N = 100010;

int n, m, w[N];
int len;
int ans[N];
int cnt[N], sum[N];//cnt[]是这个数出现次数
//sum[]是对值域区间分块
struct Query
{
    int id, l, r;
    int y0, y1;
}q[N];
int get(int x)
{
    return x / len;
}
bool cmp(const Query& a, const Query& b)
{
    if(get(a.l) != get(b.l)) return get(a.l) < get(b.l);
    if(get(a.l) % 2 == 0) return a.r < b.r;
    return a.r > b.r;
}
void add(int x)
{
    if( ++ cnt[x] == 1) sum[get(x)] ++;
}
void del(int x)
{
    if( -- cnt[x] == 0) sum[get(x)] --;
}
int query(int l, int r)
{
    int res = 0;
    if(get(l) == get(r))
    {
        for(int i = l; i <= r; i ++ ) res += (cnt[i] >= 1);
    }
    else
    {
        int i = l, j = r;
        while(get(i) == get(l)) res += (cnt[i] >= 1), i ++;
        while(get(j) == get(r)) res += (cnt[j] >= 1), j --;
        for(int k = get(i); k <= get(j); k ++) res += sum[k];
    }
    return res;
}
void solve()
{
    memset(cnt, 0 ,sizeof cnt);
    memset(sum, 0, sizeof sum);

    int n, m;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);

    len = sqrt((double)n * n / m);

    for(int i = 1; i <= m; i ++ )
    {
        scanf("%d%d%d%d", &q[i].l, &q[i].y0, &q[i].r, &q[i].y1);
        q[i].id = i;
    }

    sort(q + 1, q + 1 + m, cmp);

    for(int k = 1, i = 0, j = 1; k <= m; k ++)
    {
        int l = q[k].l, r = q[k].r, id = q[k].id;
        while(i < r) add(w[ ++ i]);
        while(j > l) add(w[ -- j]);
        while(i > r) del(w[i -- ]);
        while(j < l) del(w[j ++ ]);
        ans[id] = query(q[k].y0, q[k].y1);
    }
    for(int i = 1; i <= m; i ++) printf("%d\n", ans[i]);
}
int main()
{
    int t;
    scanf("%d", &t);
    while(t --) solve();

    return 0;
}