codeforces 292 E. Copying Data (染色问题,线段树lazy标记模板题)

x题目链接

题意:给出两个数组,每个数组n个数,分别为a和b,给出m个操作,操作有两种类型,第一种是给出x,y,k,表示从a数组的x坐标开始复制k个数到b数组的y到y+k-1。

第二种操作是给出x,询问当前b[x]是多少。

对于每个第二种操作,输出结果。

 

思路:第一次写lazy标记的线段树。

今天突然就顿悟了。。。其实lazy标记的思想大概就是。。

对于某段区间的更新,如果没有查询到这段区间中任何一个数的时候。。。那么这个更新其实是无所谓的。。。

(让我想到了那个脑洞,就是整个世界都是一段程序,为了让你不察觉异常并且耗费尽量少的资源,所有场景只有在有人观测的时候才会被加载,不观测就用很少的资源随便处理一下233)

所以lazy标记,也叫延迟标记,就是只有当查询到某个节点的时候,才去把之前的修改更新,不然不更新(就好像有人观测的时候,上帝才把某个场景的代码写出来)

这道题除了延迟标记这个点外,还用到了染色问题的经典做法。

所谓染色问题,这里说的是一种区间覆盖问题,每次用一个颜色覆盖某段区间,最后询问某一点是什么颜色(大概是这样…?

回到这道题,具体做法是,记录每次覆盖操作的位移差,然后用线段树维护某个点最后被覆盖的时间(也可以形象得说被染成了什么颜色,染的颜色种类和时间对应)

这样,每次询问b[x]的时候,我们可以查询x位置最后是被染成了什么颜色,然后根据之前记录的位移差信息,就可以得到相应的答案。

这是一种经典做法,这类问题具有一定普遍性,注意体会。

 

以及,之前对lazy标记有一个错误得认识,以为lazy是基于线段树本身数组的一个辅助数组。。。但是做完这道题后感觉。。。

之前写的单点更新的线段树数组tree和现在的lazy标记的数组应该是同等地位。。。。PushDown和PushUp大概也是同等地位。。。就是说。。。可以只出现PushDown和lazy数组不出现PushUp和tree.

还有一些写法上的注意,见代码注释。

 

 

 

 

 

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz