【BZOJ2653】middle

对于每个询问显然可以二分答案,将大于等于答案的数设为\(1\),小于答案的数设为\(-1\),那么就是查询是否存在一段和不小于\(0\)。

可以拆成三部分询问:\((b,c)\)的和,\([a,b]\)的最大后缀加上\([c,d]\)的最大前缀。

显然可以用线段树查询。

那么对于每个二分值预处理其对应的线段树。因为每棵线段树对于上一棵的更改只有一条链,可持久化即可。

说点什么

您将是第一位评论人!

提醒
wpDiscuz