娱乐 每 日 算 法 挑 战 【第F期】

[Mr.K 018]

已经出到第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模式中则可能会相同。

[yhz012]

暴力确实能暴力打表做……但是大概会比较痛苦

感觉我需要一些精妙的数据结构……

 

简单难度大概还好说？

给定q a b

倒序遍历之前的所有q x y c。我们会有4种情况

0. x y 和 a b 完全不搭界，那直接丢掉就好了，不用管

1. x < a < b < y，那ab区间直接被完全涂色了，所以之前无论做过什么都不影响了，倒序遍历到此为止，返回即可

2. x < a < y < b 或者 a < x < b < y，也就是单侧被涂了颜色，那我们需要记录单侧的位置y 或者 x，往前遍历的时候，如果再有类似的情况，比y还小或者比x还大的情况已经被盖住了，所以不用考虑了（可以理解为是一个窗口不断往中间缩）

3. a < x < y < b，即涂色在中间，类似于上一个情况，但是这回可以理解为一个窗口往两侧涨

 

2 和 3 混在一起的时候，如果这两个窗口的并集已经盖住了整个ab区间了，那直接可以停了，因为这意味着整条绳子已经在这个时候全都被重刷了一遍了

不过2和3混在一起应该还有一些情况需要排除掉……

比如

p 1 100 0

p 60 100 1

p 0 50 2

p 20 80 3

p 40 60 4

p 0 30 5

很显然中间的p 0 50 2实际上已经全都被盖住了，但是按上文所述会被计入

四月 27, 2020，由yhz012修改

[Mr.K 018]

6 小时前, yhz012 说道:

暴力确实能暴力打表做……但是大概会比较痛苦

感觉我需要一些精妙的数据结构……

 

简单难度大概还好说？

给定q a b

倒序遍历之前的所有q x y c。我们会有4种情况

0. x y 和 a b 完全不搭界，那直接丢掉就好了，不用管

1. x < a < b < y，那ab区间直接被完全涂色了，所以之前无论做过什么都不影响了，倒序遍历到此为止，返回即可

2. x < a < y < b 或者 a < x < b < y，也就是单侧被涂了颜色，那我们需要记录单侧的位置y 或者 x，往前遍历的时候，如果再有类似的情况，比y还小或者比x还大的情况已经被盖住了，所以不用考虑了（可以理解为是一个窗口不断往中间缩）

3. a < x < y < b，即涂色在中间，类似于上一个情况，但是这回可以理解为一个窗口往两侧涨

 

2 和 3 混在一起的时候，如果这两个窗口的并集已经盖住了整个ab区间了，那直接可以停了，因为这意味着整条绳子已经在这个时候全都被重刷了一遍了

不过2和3混在一起应该还有一些情况需要排除掉……

比如

p 1 100 0

p 60 100 1

p 0 50 2

p 20 80 3

p 40 60 4

p 0 30 5

很显然中间的p 0 50 2实际上已经全都被盖住了，但是按上文所述会被计入

这个题这么做意外的也可以？

hard难度应该不能这么做，这个题本来是个数据结构题来着

[yhz012]

10 小时前, Mr.K 018 说道:

这个题这么做意外的也可以？

hard难度应该不能这么做，这个题本来是个数据结构题来着

hard难度其实可以再做个hash set，每次计数的时候看一下有没有这个颜色，没有就加进来，有就丢掉。

 

不过果然是数据结构题……我想想怎么用数据结构解决好了