目录
目录简介
在练习数据结构中，我们经常看到有以下操作的题：
- 求一个区间 \([l,r]\) 的数字种数。
- 求一个区间 \([l,r]\) 某一个数字 \(k\) 的出现次数。
我们称这一类问题为“数颜色模型”
例子：
-
\(\cdots\)
一些解法
莫队/带修莫队
时间复杂度：莫队 \(O(m\sqrt{n})\)，带修莫队 \(O(mn^{\frac{2}{3}})\)。
先开一个桶 \(b\)，如果添加一个数 \(v\)，那么 \(b[v]\) 加上 \(1\)。当然，如果加完后 \(b[v] = 1\)，那么就出现了一个新颜色。删除元素 \(v\) 时，\(b[v]=b[v]-1\)，如果减完后 \(b[v]=0\)，那么就消失了一个颜色。
关键代码如下：
void add(int x){
times[x]++;
if(times[x]==2){
++tans;
}
}
void remove(int x){
times[x]--;
if(times[x]==1){
--tans;
}
}
题目：
- P4113 [HEOI2012] 采花 \(133\) 分。
- P1903 [国家集训队] 数颜色 / 维护队列
- P1972 [SDOI2009] HH的项链 \(28\) 分
- P2709 小B的询问
珂朵莉树
时间复杂度均摊 \(O(m\log\log n)\)；最差 \(O(mn)\)。
由于珂朵莉树本质上是暴力，自然可以维护颜色。只要有区间染色。
关键代码：
int times(int l, int r, int c) {
int res = 0;
odti rs = split(r + 1);
odti ls = split(l);
for (odti now = ls; now != rs; now++) {
if (now->v == c) {
res += (now->r - now->l + 1);
}
}
return res;
}
题目：
- LibreOJ6284. 数列分块入门 8
- 校内测试 lfxxx的幸运数 \(40\) 分