已经出到第15期啦!下一期难道就需要两位数了吗?!
时间过得好快啊。
今天这道题想做出来不难,但是想要跑得快(西方记者:?)的话,需要一点知识和技巧才行。
召唤阵:
@yhz012 @inuisanaa @ZERC @随性而为 @NianRuoshui @摸鱼奇才咖啡喵
第15期 给绳子染色
有一根绳子,我们要把它涂上各种颜色用来装饰。可以把绳子想象成一段一段的,一共有n段,每次涂色都会涂连续的若干段。比如,先把第1段到第10段涂成红的,仔把第5段到第20段涂成绿的,再把第3段到第7段涂成白的,等等。不用在乎每种颜色都叫什么,我们用一个数字来表示颜色。
涂了一段时间颜色之后,涂色的人也搞不清楚绳子被涂成啥样了。现在他想问问你,指定的两个段之间(包含这两个段),有多少种不同的颜色?
输入
输入有多行,请读取到文件尾。
第一行是绳子的总长度n和颜色的种数k。接下来若干行,每行可能有两种情况:
p x y c,表示从第x段到第y段(含x, y),涂上第c种颜色;
q x y,表示询问第x段和第y段(含x, y)之间的颜色种数。
输出
对每个询问输出一行一个整数,表示颜色种数。
难度选择
本题分为两种难度:easy和hard。在easy模式中,保证任意两次涂上的颜色不相同;在hard模式中则可能会相同。