codeforces 515 E. Drazil and Park ( 线段树区间合并)

题目链接

题意:圆上,询问任意一段弧中,任意两点的距离+两点的权值和的最大值。

思路:

1.环先拆成串,复制1..n到后面,变成1..2n。

化简公式:

2 * h[u] + 2 * h[v] + dist(u, v) = 2 * h[v] + d[1] + d[2] + … + d[v-1] + 2 * h[u] – (d[1] + d[2] + … + d[u-1]).
设A[v] = 2 * h[v] + d[1] + d[2] + … + d[v-1], B[u] = 2 * h[u] – (d[1] + d[2] + … + d[u-1]).

Another important thing is that Lu + Rv always bigger than Lv + Ru when u < v.

So we can almost solve the problem just by finding the maximum value of Lu and Rv by RMQ separately and sum them up.

但是至少由两颗树。。。所以要保证u!=v…

这也是本题的难点。。。

 

做法是,线段树维护三个域。

分别表示某区间A的最大值,某区间B的最大值,某区间A+B的最大值(且保证A和B不属于同一个区间)

如何保证呢? 每次合并的时候。。。合并不同的区间就好了。。。

具体见代码

注意体会这种区间合并的思想。。。

以及query的时候。。。做法类似于:bzoj1756题目链接

说点什么

您将是第一位评论人!

提醒
wpDiscuz