洛谷 P2486 [SDOI2011]染色

洛谷 P2486 [SDOI2011]染色

洛谷传送门

题目描述

给定一棵 nn 个节点的无根树,共有 mm 个操作,操作分为两种:

  1. 将节点 aa 到节点 bb 的路径上的所有点(包括 aa 和 bb)都染成颜色 cc
  2. 询问节点 aa 到节点 bb 的路径上的颜色段数量。

颜色段的定义是极长的连续相同颜色被认为是一段。例如 112221 由三段组成:112221

输入格式

输入的第一行是用空格隔开的两个整数,分别代表树的节点个数 nn 和操作个数 mm

第二行有 nn 个用空格隔开的整数,第 ii 个整数 w_iw**i 代表结点 ii 的初始颜色。

第 33 到第 (n + 1)(n+1) 行,每行两个用空格隔开的整数 u, vu,v,代表树上存在一条连结节点 uu 和节点 vv 的边。

第 (n + 2)(n+2) 到第 (n + m + 1)(n+m+1) 行,每行描述一个操作,其格式为:

每行首先有一个字符 opo**p,代表本次操作的类型。

  • 若 opo**pC,则代表本次操作是一次染色操作,在一个空格后有三个用空格隔开的整数 a, b, ca,b,c,代表将 aa 到 bb 的路径上所有点都染成颜色 cc
  • 若 opo**pQ,则代表本次操作是一次查询操作,在一个空格后有两个用空格隔开的整数 a, ba,b,表示查询 aa 到 bb 路径上的颜色段数量。

输出格式

对于每次查询操作,输出一行一个整数代表答案。


题解:

精髓在于线段树维护颜色块。

可以参考小白逛公园的维护方式,在维护答案的同时维护区间左右端点的颜色。显然的是,在区间合并的时候,如果左儿子的右端点颜色等于右儿子的左端点颜色,那么就需要把答案-1.

就这么维护就好了。

原文地址:https://www.cnblogs.com/fusiwei/p/13851120.html