数据结构中的数颜色模型

目录

简介

在练习数据结构中，我们经常看到有以下操作的题：

• 求一个区间 ([l,r]) 的数字种数。
• 求一个区间 ([l,r]) 某一个数字 (k) 的出现次数。

我们称这一类问题为“数颜色模型”

例子：

• P4113 [HEOI2012] 采花

• P1903 [国家集训队] 数颜色 / 维护队列

• P2486 [SDOI2011]染色

• P3939 数颜色

• P1972 [SDOI2009] HH的项链

• P2709 小B的询问

• LibreOJ6284. 数列分块入门 8

• P7735 [NOI2021] 轻重边

• P4117 [Ynoi2018] 五彩斑斓的世界

• P4690 [Ynoi2016] 镜中的昆虫

• 校内测试 lfxxx的幸运数

• (cdots)

一些解法

莫队/带修莫队

时间复杂度：莫队 (O(msqrt{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(mloglog 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) 分