你知道颜色有几种数法吗？
（孔乙己显出极高兴的样子，将两个指头的长指甲敲着柜台，点头说，“对呀对呀！……颜色有四样数法，你知道么？）
咳咳咳
最近做了好多数颜色的题，总结一波
数颜色题目的题意可以大致总结为：
有一段序列，每个点都有一个颜色（权值），求进行一些更改操作后区间的颜色信息。
（$n$为序列长度，$m$为操作次数，颜色的值域为$V$）
1. ZBT的游戏：
区间修改，区间查询颜色种类，$n,m \leq 10^5 , V \leq 256 $
区间较大，颜色种类较少，操作较复杂，考虑对序列开线段树维护区间颜色是否出现，可以使用$bitset$实现
2. 数颜色 / 维护队列：
单点修改，区间查询颜色种类，$n,m \leq 5*10^4, V \leq 10^6$
区间较小，颜色种类较多，操作简单，考虑使用带修莫队加分块解决
（当然你想用树状数组套主席树，线段树套平衡树我也不拦你）
3.数颜色：
交换相邻颜色，查询区间某种颜色个数，$n,m \leq 3*10^5,V \leq 3*10^5$
区间较大，颜色种类较多，但操作简单，且查询信息简单
对每个颜色开一个$vector$，查询时二分对应颜色的$vector$中的区间位置，修改时颜色位置++--就好了
也可以用动态开点线段树代替$vector$
（同样可以用树套树……）
4.作业：
无修改，查询区间内$\geq a$且$\leq b$的数的个数，$n \leq 10^5,V \leq 10^5$
因为无修改，莫队加值域分块即可
然后是树上的题：
（$n$为节点数，$m$仍为操作次数，颜色的值域为$V$）
5.染色：
$u$到$v$路径颜色修改，$u$到$v$路径颜色段数量查询，$n,m \leq 10^5, V \leq 10^9$
树上操作，当然是树链剖分了，剖完套个线段数维护一下颜色段数就好了
6.模板：
每个节点可以放$k_u$个小球，每次操作对从$u$到根的链上每个节点放一个颜色为$c$的小球
若超出节点容量，则不放，查询某节点的小球颜色有多少种
保证先进行所有的操作，再进行一些查询
$n,m \leq 10^5, V \leq 10^5$
对每个节点开一个以时间为下标的线段树
操作结束后从下到上启发式合并线段树，计算每个节点的答案
具体解法：noip模拟测试10
7.影魔：
给一棵树，查询以$u$为根的子树内与$u$距离不超过$d$的点的颜色种类数，$n,m \leq 10^5, V \leq 10^5$
（如果$V \leq 10^9$的话离散化一下就一样了）
目前只会离线做法……
离线：对于每个节点维护一颗线段树，下标为颜色，权值为该颜色的最浅深度（子树内）
再对全局开一颗树状数组，下标为深度，权值为种类数
当进入某节点时，查询该节点所有询问，即子树外对答案的影响
当即将离开某节点时，再次查询，将本次查询值减去上次查询值即为$answer$
对于线段树，只需要一层层向上合并即可
在线：好像是链并？
类似的一道题：谈笑风生 （主要思想：用主席树解决子树内距离不超过$k$的信息统计问题）