写一个感觉比较详细(萌新友好向)的莫队做法…复杂度 $O(n\sqrt m+m\sqrt n)$ 。
考虑直接莫队的话，需要支持查询某个值域区间中的数，需要上树状数组，但这样带 $\log$ 。
于是考虑一下莫队的本质，即莫队的复杂度分析，本质上分析的是 $l,r$ 移动的复杂度，也就是修改的复杂度。所以莫队可以本质上看成一个 $O(n\sqrt m)$ 修改，$O(m)$ 询问的数据结构。观察到询问数较少，于是可以用一个可以快速修改，低速查询的 ds 来维护值域，那这自然就是值域分块，最终复杂度 $O(n\sqrt m+m\sqrt n)$ 。
以下是补充内容：
____
1、莫队的复杂度分析
令 $m$ 为操作数，$B$ 为块大小。考虑对于一个块内的 $l$，其 $r$ 是单增的，于是考虑如下：
- 左端点，在块内可能会一前一后这样设置，这样复杂度被卡到最满，为 $O(m\cdot B)$ ；
- 右端点，考虑各块内的询问显然都可以做到单块 $O(n)$，所以不需要考虑 $m$ 的贡献，即右端点移动的复杂度就是 $\frac{n}{B}\cdot n=\frac{n^2}{B}$。
均值一下发现 $m\cdot B+\frac{n^2}{B}\geq 2\sqrt{n^2m}=O(n\sqrt m)$ ，此时有 $m\cdot B=\frac{n^2}{B}$，解得 $B=\frac{n}{\sqrt m}$ .
所以取块大小为 $\frac{n}{\sqrt m}$ 时达到理论最优，复杂度为 $O(n\sqrt m)$ 。
____
2、值域分块的正确打开方式
观察到我们本质上需要一个值域上 $O(1)$ 单点加/减，$O(\sqrt n)$ 区间询问的结构，那就是普通的分块了。考虑分块维护块内和和单点值，修改的时候 $O(1)$ 修改点值和块值，询问就是朴素询问(for 过去)即可。
____
然后本题需要分别维护出现次数和是否出现，分别维护即可。
```cpp
#include <bits/stdc++.h>
using namespace std ;
const int N = 200010 ;
void debug(int *tp, int minn, int maxn, char c){
for (int i = minn ; i <= maxn ; ++ i)
cout << tp[i] << " " ; cout << c ;
}
int B ;
int V ;
int n, m ;
int bl[N] ;
int blv[N] ;
int res[N] ;
int ans[N] ;
int sum[N] ;
int sumr[N] ;
int sump[N] ;
int base[N] ;
struct query{
int id ;
int l, r ;
int a, b ;
}q[N] ;
bool comp(query a, query b){
return (bl[a.l] ^ bl[b.l]) ? bl[a.l] < bl[b.l] :
((bl[a.l] & 1) ? a.r < b.r : a.r > b.r) ;
}
void del(int p){
sump[base[p]] -- ;
sumr[blv[base[p]]] -- ;
if (sump[base[p]] <= 0) -- sum[blv[base[p]]] ;
}
void add(int p){
sump[base[p]] ++ ;
sumr[blv[base[p]]] ++ ;
if (sump[base[p]] <= 1) ++ sum[blv[base[p]]] ;
}
int get_ans(int l, int r){
int ret = 0 ;
r = min(r, V) ;
if (l > V) return 0 ;
int nl = blv[l] + 1 ;
int nr = blv[r] - 1 ;
if (blv[l] == blv[r]){
for (int i = l ; i <= r ; ++ i)
ret += (bool)sump[i] ; return ret ;
}
for (int i = nl ; i <= nr ; ++ i) ret += sum[i] ;
for (int i = l ; blv[i] == blv[l] && l <= V ; ++ i) ret += (bool)sump[i] ;
for (int i = r ; blv[i] == blv[r] && r >= 0 ; -- i) ret += (bool)sump[i] ;
return ret ;
}
int get_res(int l, int r){
int ret = 0 ;
r = min(r, V) ;
if (l > V) return 0 ;
int nl = blv[l] + 1 ;
int nr = blv[r] - 1 ;
if (blv[l] == blv[r]){
for (int i = l ; i <= r ; ++ i)
ret += sump[i] ; return ret ;
}
for (int i = nl ; i <= nr ; ++ i) ret += sumr[i] ;
for (int i = l ; blv[i] == blv[l] && l <= V ; ++ i) ret += sump[i] ;
for (int i = r ; blv[i] == blv[r] && r >= 0 ; -- i) ret += sump[i] ;
return ret ;
}
int main(){
cin >> n >> m ;
B = 1.0 * n / sqrt(m) + 1 ;
for (int i = 1 ; i <= n ; ++ i)
scanf("%d", &base[i]), V = max(V, base[i]), bl[i] = i / B ;
for (int i = 1 ; i <= m ; ++ i)
scanf("%d%d%d%d", &q[i].l, &q[i].r, &q[i].a, &q[i].b), q[i].id = i ;
sort(q + 1, q + m + 1, comp) ;
int l = 1, r = 0 ; B = sqrt(V) + 1 ;
for (int i = 0 ; i <= V ; ++ i) blv[i] = i / B ;
for (int i = 1 ; i <= m ; ++ i){
int a = q[i].a, b = q[i].b ;
while (l < q[i].l) del(l ++) ;
while (l > q[i].l) add(-- l) ;
while (r < q[i].r) add(++ r) ;
while (r > q[i].r) del(r --) ;
res[q[i].id] = get_res(a, b) ;
ans[q[i].id] = get_ans(a, b) ;
}
for (int i = 1 ; i <= m ; ++ i)
printf("%d %d\n", res[i], ans[i]) ; return 0 ;
}
```
快来夸我码风! (超自豪
~~我是一个刚开始学 lxl 深刻理论的萌新，不要 d 我~~