Description
给定一个长为 (n) 的正整数序列，(m) 个询问。
每个询问给出四个正整数 ((l, r, a, b)) ，要求 区间 ([l,r]) 内在值域 ([a,b]) 中的数字的个数以及数字种类数。
Hint
(1le n, mle 10^5, ext{所有数字}in[1, 10^5])
Solution 1
CDQ 分治。
仿照 HH的项链 的做法，先求出每个位置的数字前面出现的的位置 ( ext{pre}_i)。没有记作 0。
然后 ([l,r]) 中所有满足 ( ext{pre}_i < l) 的都是区间中这个数字第一次出现的。
这就好办了，将数列中每一个元素记作一个三维点，(x, y, z) 坐标分别为位置，值，( ext{pre}) 。
那么对于一个询问 ((l, r, a, b)) ，相当于就是求 (1le xle r ext{ and } ale yle b ext{ and } 0le z < ext{pre}_l) 的点的数量，即三维数点。
第一问的话可以在做第二问时计算好。
于是 cdq分治 自然可做。
- 时间复杂度：(O((n+m)log^2 n))
- 空间复杂度：(O(n+m))
- 是否在线：否
Solution 2
K-D Tree。
既然可以转换为 三维数点问题 ，那么想必 KDT 也是可以的。
而且可以做到在线。
- 时间复杂度：(O(mn^{frac{2}{3}}) - Omega(mlog n))
- 空间复杂度：(O(n))
- 是否在线：是
Solution 3
莫队，值域分块。
看到区间数颜色，很容易想到莫队算法。唯一的限制就是值域为 ([a,b])。
树状数组？修改带 (log) ，还是不够优秀。
其实可以值域分块：将整段值域分成若干个块，然后在块中维护信息即可。
这样可以 (O(1)) 修改，(O(sqrt{n})) 查询。
- 时间复杂度：(O(nsqrt{m} + msqrt{n}))
- 空间复杂度：(O(n + m))
- 是否在线：否
Code
（据说块长为 (frac{n}{sqrt{m}}) 最快？反正 (sqrt{n}) 过了 qwq）
/*
* Author : _Wallace_
* Source : https://www.cnblogs.com/-Wallace-/
* Problem : Luogu P4396 AHOI2013 作业
*/
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 1e5 + 5;
const int Q = 1e6 + 5;
const int T = 500;
struct Query {
int l, r, pos;
int a, b;
} qry[Q];
int ans[2][Q];
int ary[N];
int belong[N], b;
int n, q;
int total[T], cnt[N], sum[N];
int L = 1, R = 0;
inline void inc(int p) {
if (cnt[ary[p]]++ == 0) total[belong[ary[p]]]++;
sum[belong[ary[p]]]++;
}
inline void dec(int p) {
if (--cnt[ary[p]] == 0) total[belong[ary[p]]]--;
sum[belong[ary[p]]]--;
}
inline int calc1(int a, int b) {
int ret = 0;
if (belong[a] == belong[b]) {
for (register int i = a; i <= b; i++)
ret += cnt[i];
return ret;
}
for (register int i = a; belong[i] == belong[a]; i++)
ret += cnt[i];
for (register int i = b; belong[i] == belong[b]; i--)
ret += cnt[i];
for (register int i = belong[a] + 1; i < belong[b]; i++)
ret += sum[i];
return ret;
}
inline int calc2(int a, int b) {
int ret = 0;
if (belong[a] == belong[b]) {
for (register int i = a; i <= b; i++)
ret += (cnt[i] > 0);
return ret;
}
for (register int i = a; belong[i] == belong[a]; i++)
ret += (cnt[i] > 0);
for (register int i = b; belong[i] == belong[b]; i--)
ret += (cnt[i] > 0);
for (register int i = belong[a] + 1; i < belong[b]; i++)
ret += total[i];
return ret;
}
inline void select(int l, int r) {
while (L < l) dec(L++);
while (L > l) inc(--L);
while (R < r) inc(++R);
while (R > r) dec(R--);
}
inline bool operator < (const Query& x, const Query& y) {
return belong[x.l] != belong[y.l] ? belong[x.l] < belong[y.l] : x.r < y.r;
}
signed main() {
ios::sync_with_stdio(false);
cin >> n >> q, b = ceil(sqrt(n));
for (register int i = 1; i <= n; i++)
cin >> ary[i], belong[i] = (i - 1) / b + 1;
for (register int i = 1; i <= q; i++)
cin >> qry[i].l >> qry[i].r >> qry[i].a >> qry[i].b, qry[i].pos = i;
sort(qry + 1, qry + 1 + q);
for (register int i = 1; i <= q; i++) {
select(qry[i].l, qry[i].r);
ans[0][qry[i].pos] = calc1(qry[i].a, qry[i].b);
ans[1][qry[i].pos] = calc2(qry[i].a, qry[i].b);
}
for (register int i = 1; i <= q; i++)
cout << ans[0][i] << ' ' << ans[1][i] << endl;
return 0;
}
Solution 4
数列分块。
咕咕咕