【JZOJ 4273】 【NOIP2015模拟10.28B组】圣章-精灵使的魔法语

题目大意:

给定一个括号队列,(m) 个操作:改变一段区间的所有括号或查询一段区间还需多少括号。

正文:

考虑用线段树维护括号串中一个区间内多余的左右括号数(用 (left,right) 代替)。

(egin{aligned} herefore t_{x}.left & =t_{2x+1}.left+max{t_{2x}.left-t_{2x+1}.right,0}\ t_{x}.right & = t_{2x}.right+max{t_{2x+1}.right-t_{2x}.left,0}end{aligned})

接下来就是线段树基本操作。

原文地址:https://www.cnblogs.com/GJY-JURUO/p/13466569.html