vijos1448

题目链接

原网站:

线段树练习_vijos1448

OJ上有加强数据版的,不用树状数组||线段树过不了的

线段练习_vijos1448强化数据版

题解

在vijos上找了一道线段树裸题…

信心满满一顿啪啪啪啪啪啪啪

写了个区间修改区间查询下传标记维护区间最大值的线段树..

过样例一交,才发现理解错题意了.


用括号序列的思想来解决.

其实就是询问区间相交的问题.

我们可以把区间修改看作为对左端点和右端点的单点修改.

更新区间[a,b]时,点a记录左括号数,点b记录右括号数,查询区间[a,b]时,即为b之前(包括b)的左括号数-a之前的右括号数.

最后输出就好了.

搞清楚该查询哪两个区间就好了..


By:Wahacer

2017.12.5

16:01

发表评论

电子邮件地址不会被公开。 必填项已用*标注