codeforces 145 E. Lucky Queries (线段树lazy标记)

题目链接

题意:给出一串只由数字’4’和’7’组成的串。两种操作,一种是询问整个串中最长非下降子序列的长度,另一种给出区间[l,r],将区间中的没个数反转,反转的定义为,4变成7,7变成4.

思路:线段树lazy标记。

线段树的域记录5个信息,c4,c7,c47,c74,flip,a分别表示4的个数,7的个数,非下降子序列的个数,非上升的子序列的个数,以及该区间是否被翻转。

纠结了很久PushUp操作。。。。

c4和c7倒是没什么疑问。。。。

一开始觉得c47是由三部分的最大值更新得到的。。。

left.c4+right.c47,left.c4+right.c7,left.c47+right.c7…

但是样例过不了。。。

纠结了半天发现。。。

比如4774,4444是左右两个区间的时候。。。。

c47最大是5.。。但是left.c4 + right.c7=6,比正确答案大。

原因是。。一个区间中4的位置可能是分散的。。。这样只有某段连续出现的4对答案的贡献是正确的。。。

所以只有区间长度为1的时候c4+c7的更新方式才是合法的。。。

我们不妨在初始化的时候。。。。在线段树的叶子节点直接设置c47为1(当然相应地c74也要为1)

另外一个收获是。。。线段树对于区间的操作(对于点的操作也是同样)

不一定是某种常见的定义过的操作(求和啊,最大值最小值啊之类的)

也可能是某种自定义的操作。。。

比如这道题中的flip操作。。。

就是对区间的一个自定义的操作。。。

 

 

 

 

 

 

说点什么

您将是第一位评论人!

提醒
wpDiscuz