你知道颜色有几种数法吗?
(孔乙己显出极高兴的样子,将两个指头的长指甲敲着柜台,点头说,“对呀对呀!……颜色有四样数法,你知道么?)
咳咳咳
最近做了好多数颜色的题,总结一波
数颜色题目的题意可以大致总结为:
有一段序列,每个点都有一个颜色(权值),求进行一些更改操作后区间的颜色信息。
(n为序列长度,m为操作次数,颜色的值域为V)
1. :
区间修改,区间查询颜色种类,$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$
对每个节点开一个以时间为下标的线段树
操作结束后从下到上启发式合并线段树,计算每个节点的答案
具体解法: