华师一附中OI组

标题: 线段树4（统计线段数目） [打印本页]

作者: admin 时间: 2018-5-13 01:03
标题: 线段树4（统计线段数目）
【题意】
有n(1~100000)个连续的格子，编号为1……n，每个格子的颜色有3种（分别是1、2、3）。
有m（1~100000）操作，操作有2种：
1 x y k：表示第x个格子至第y个格子全染色为k（1<=k<=3)
2 x y:表示询问第x个格子至第y个格子有多少条线段（相邻两个格子的颜色相同则同属一条线段）。
【输入格式】
第一行n和m。
第二行n个数，分别表格n个格子的颜色。
下来m行，每行表示一个操作。
【输出格式】
遇到操作2，则输出答案

【样例输入】
5 5
2 1 1 2 1
2 1 5
1 4 4 1
2 1 5
1 1 1 1
2 1 5
【样例输出】
4
2
1

欢迎光临华师一附中OI组 (http://hsyit.cn/)