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

[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修改

[yhz012]

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

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

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

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

 

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