10.CF515E Drazil and Park 简单线段树

10.CF515E Drazil and Park 简单线段树

个人Limitの线段树题单题解主目录：Limitの线段树题单 题解目录_HeartFireY的博客-CSDN博客

给定一个环， i − i + 1 i-i+1 i−i+1之间的距离给定，每个点有点权 h i h_i hi​ 每次询问会禁止经过一个区间，求两个点 ( s , t ) (s, t) (s,t)能够使得 2 ∗ ( h s + h t ) + d i s ( s , t ) 2 * (h_s + h_t) + dis(s, t) 2∗(hs​+ht​)+dis(s,t)取得最大值 求这个最大值

洛谷传送门：CF515E Drazil and Park - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

CF传送门：E. Drazil and Park (codeforces.com)

题目分析

• 给定一个环， i − i + 1 i-i+1 i−i+1之间的距离给定，每个点有点权 h i h_i hi​

• 每次询问会禁止经过一个区间，求两个点 ( s , t ) (s, t) (s,t)能够使得 2 ∗ ( h s + h t ) + d i s ( s , t ) 2 * (h_s + h_t) + dis(s, t) 2∗(hs​+ht​)+dis(s,t)取得最大值

• 求这个最大值

把式子转化一下：

• 对 d i s dis dis求前缀和 d d dd dd，则 d i s ( l , r ) = d d [ r ] − d d [ l ] dis(l, r)=dd[r] - dd[l] dis(l,r)=dd[r]−dd[l]

• 原式化为 d d [ r ] − d d [ l ] + 2 h [ l ] + 2 h [ r ] = ( d d [ r ] + 2 h [ r ] ) − ( d d [ l ] − 2 h [ l ] ) dd[r] - dd[l] + 2h[l] + 2h[r] = (dd[r] + 2h[r]) - (dd[l] - 2h[l]) dd[r]−dd[l]+2h[l]+2h[r]=(dd[r]+2h[r])−(dd[l]−2h[l])

• 对 d d [ r ] + 2 h [ r ] dd[r] + 2h[r] dd[r]+2h[r]维护区间最大值，对 d d [ l ] − 2 h [ l ] dd[l] - 2h[l] dd[l]−2h[l]维护区间最小值即可

于是就变成了线段树维护区间最大值最小值的过程。在计算过程中对答案取最大值即可。

Code

#include 
#pragma gcc optimize("O2")
#pragma g++ optimize("O2")
#define int long long
#define endl '\n'
using namespace std;

namespace ffastIO {
	const int bufl = 1