下载掌阅APP，畅读海量书库
立即打开
题目描述（POJ2777）： 有一个长 L 厘米的电路板，可以将板均分为 L 段（1～ L ），每段长1厘米。现在给电路板上色，每段只有一种颜色。可以在电路板上执行两种操作：①C a b c ，从 a 段到 b 段涂色为 c ；②P a b ，输出 a 段和 b 段之间不同颜色的数量（包括 a 、 b ），颜色编号为1～ T 。开始时，在电路板上涂有颜色1。
输入： 第1行包含3个整数 L （1≤ L ≤10 5 ）、 T （1≤ T ≤30）和 O （1≤ O ≤10 5 ，表示操作次数）。接下来的 O 行，每行都包含C a b c 或P a b （ a 、 b 、 c 是整数， a 可以大于 b ）。
输出： 按顺序单行输出操作结果。
题解： 根据输入样例，长度 L =2，颜色数 T =2，操作次数 O =4，初始时均为1号色。
（1）C 1 1 2：将1-1段涂2号色。
（2）P 1 2：统计1-2段的颜色数，输出颜色数2。
（3）C 2 2 2：将2-2段涂2号色。
（4）P 1 2：统计1-2段的颜色数，输出颜色数1。
本题包括区间修改、区间查询，可以用线段树解决。由于本题的区间查询只需统计该区间的颜色数，因此并不需要将区间内的所有颜色求和。
（1）创建线段树，树根的颜色为1（相当于懒标记），其他节点的颜色为0。
（2）查询[ l , r ]区间的颜色数。若树根rt颜色不为0，则ans[tree[rt].color]=true，返回；否则递归查询左右子树。统计所有颜色 k ，若ans[ k ]为真，则tot++，最后输出tot即可。
（3）更新[ l , r ]区间的颜色为 c 。若树根正好为该区间，则将根节点的颜色修改为 c ，tree[rt].color= c ，返回；否则树根颜色下传（左右子树等于根的颜色，将根的颜色修改为0）；递归更新左右子树；返回时颜色统一（若左右子树颜色相同，则将树根的颜色也修改为该颜色）。
本题秘诀：
· 查询时，遇到第1个颜色非0节点，标记后返回，否则递归查询左右子树；
· 更新时，将区间的颜色号修改为 c ，在查找过程中颜色下传，回退时颜色统一。
（1）创建线段树，树根的颜色为1（相当于懒标记），其他节点的颜色为0。
（2）P 1 2：统计1-2段的颜色数，因为树根[1, 10]为1号色，不为0，所以令ans[1]=true，返回；统计后1-2段的颜色数为1。
（3）C 4 6 2：将4-6段涂2号色。首先搜索[4, 5]、[6, 6]区间，在搜索过程中若颜色不为0，则将其作为懒标记下传。将当前节点的懒标记下传给左右子节点，当前节点的颜色为0。
将[4, 5]、[6, 6]区间的颜色修改为2，然后返回，在返回过程中若当前节点的左右子树颜色相同，则当前节点的颜色和它们一致。
（4）P 5 8：统计5-8段的颜色数，因为树根[1, 10]的颜色为0，所以递归查询左右子树，[4, 5]的颜色为2，令ans[2]=true，返回；[6, 6]的颜色为2，令ans[2]=true，返回；[7, 7]的颜色为1，令ans[1]=true，返回；[8, 8]的颜色为1，令ans[1]=true，返回。统计后5-8段的颜色数为2。注意：查询时遇到第一个颜色不为0的节点才会返回。
（5）C 5 9 5：将5-9段涂1号色。首先搜索[5, 5]、[6, 8]、[9, 9]区间。在搜索过程中若颜色不为0，则将其作为懒标记下传。
将[5, 5]、[6, 8]、[9, 9]区间的颜色修改为1，然后返回。返回时[9, 10]、[6, 10]区间左右子树的颜色相同，颜色修改与其左右子树一致，均为1。
（6）P 6 7：统计6-7段的颜色数，因为树根[1, 10]的颜色为0，所以递归查询右子树，[6, 10]的颜色为1，令ans[1]=true，返回。统计后6-7段的颜色数为1。
