P14311 【MX-S8-T4】平衡三元组 题解

出题人题解，欢迎观看视频题解，打不开的把链接https://www.bilibili.com/video/BV1hhsfzYEdc/复制下来打开。

首先转化条件为 $2B_y\leq B_x+B_z$。

那么就是在区间 $l,r$ 内找三个下标 $l\leq x<y<z\leq r,2A_y\leq A_x+A_z$，最大化 $A_x+A_y+A_z$。

提示1：考虑固定 $y$ 的时候，$x,z$ 的取值。

这个时候 $x$ 肯定取到 $[l,y)$ 的最大值，同理 $z$ 取到 $(y,r]$ 的最大值。

于是可以快速得到一个 $\mathcal{O}(nq)$ 的做法，对于区间做前缀和后缀最大值，枚举 $y$ 的位置即可。

继续优化，观察 $x,y,z$ 还有什么性质。

观察到：由于 $x,z$ 覆盖了整个左右区间，那么 $x,z$ 中一定有一个是区间最大值。

根据这点，我们钦定 $a$ 是区间最大值，作为 $x$，接下来考虑 $y$ 放在什么地方，$z$ 是 $(y,r]$ 的最大值。

于是自然的想到一个特殊的 $z$，为 $(a,r]$ 的最大值，记为 $a_0$。那么 $\forall y\in(a,a_0)$ 都有 $y\leq A_{a_0}\leq A_{a}$，于是 $(a,y,a_0)$ 合法，可以贡献答案。

分析一下，到这个时候我们已经考虑了 $y\in (a,a_0)$ 的所有情况，接下来考虑 $y=a_0$ 的情况，记 $a_1$ 为 $(a_0,r]$ 的最大值，如果 $(a,a_0,a_1)$ 合法则可以贡献答案。

这个时候已经考虑 $y\in (a,a_0]$ 的所有情况。如果 $(a,a_0,a_1)$ 合法，对于 $\forall y\in(a_0,r],A_y\leq A_{a_0}$ 以及 $\forall z\in(a_0,r],A_z\leq A_{a_1}$，可以得到不会有更好的 $(a,x,y)$ 了。

如果 $(a,a_0,a_1)$ 不合法怎么办？只有继续考虑 $y\in(a_0,r]$ 的情况。

延续刚才的想法，我们先钦定 $z=a_1$，那么 $\forall y\in(a_0,a_1)$ 都有 $(a,y,a_1)$ 合法，并且可以找到 $a_2$ 是 $(a_1,r]$ 的最大值，尝试贡献 $(a,a_1,a_2)$。

可以立刻意识到我们进入了一个和刚才相似的递归子结构，到这里我们处理了 $y\in (a,a_1]$ 的所有情况。

提示2：尝试分析是否会继续递归吗？最多递归多少层？

直接分析 $2A_{a_0}> A_a+A_{a_1}$ 那么 $A_{a_1}<2A_{a_0}-A_a$。

接下来 $2A_{a_1}>A_a+A_{a_2}$，那么 $A_{a_2}<2A_{a_1}-A_a<4A_{a_0}-3A_a$。

归纳一下 $A_i< 2^iA_{a_0}-(2^i-1)A_a=A_a-2^i(A_a-A_{a_0})$。

所以如果 $A_a\not=A_{a_0}$，只会递归 $\mathcal{O}(\log V)$ 次。如果 $A_a=A_{a_0}$ 则从 $a_1$ 开始归纳也一样，如果 $A_a=A_{a_0}=A_{a_1}$ 那么 $(a,a_0,a_1)$ 就已经合法了。

总结一下只需要求区间最大值和其位置，修改只有区间加法，线段树即可解决。时间复杂度 $\mathcal{O}(q\log V\log n)$，这里认为 $qX$ 和 $V$ 同阶。

#include<bits/stdc++.h>

#define NOBUG
// #define ONLINE_JUDGE
#define il inline __attribute((always_inline)) 

#ifdef NOBUG
#define dbg(...) fprintf (stderr, __VA_ARGS__)
#else
#define dbg(...) void()
#endif

using u32=unsigned int;
using i64=long long;
using u64=unsigned long long;

const i64 INF=0x3f3f3f3f3f3f3f3fll;

#define lc (p<<1)
#define rc (lc|1)

i64 tag[1000010<<2];

struct NODE{
	i64 max;
	int pos;
	NODE operator + (const NODE &o) const{
		i64 mx=std::max(max,o.max);
		int p=0;
		if(max==mx) p=pos;
		if(o.max==mx) p=o.pos;
		return {mx,p};
	}
}tree[1000010<<2];

void down(int p,i64 x){
	tree[p].max+=x;
	tag[p]+=x;
}

void pushdown(int p){
	down(lc,tag[p]),down(rc,tag[p]);
	tag[p]=0;
}
void pushup(int p){
	tree[p]=tree[lc]+tree[rc];
}

void read(int p,int l,int r){
	if(l==r){
		tree[p]={0,l};
		scanf("%lld",&tree[p].max);
		return;
	}
	int mid=(l+r)>>1;
	read(lc,l,mid),read(rc,mid+1,r);
	pushup(p);
}

void modify(int p,int l,int r,int s,int t,int x){
	if(s<=l&&r<=t) return down(p,x);
	int mid=(l+r)>>1;
	pushdown(p);
	if(s<=mid) modify(lc,l,mid,s,t,x);
	if(mid<t) modify(rc,mid+1,r,s,t,x);
	pushup(p);
}

NODE qry(int p,int l,int r,int s,int t){
	if(s<=l&&r<=t) return tree[p];
	int mid=(l+r)>>1;
    pushdown(p);
	NODE res={-INF,0};
	if(s<=mid) res=res+qry(lc,l,mid,s,t);
	if(mid<t) res=res+qry(rc,mid+1,r,s,t);
	return res;
}

int n;

NODE qry(int l,int r,char rev){
	if(rev){
		l=n-l+1,r=n-r+1;
		std::swap(l,r);
	}
	if(l>r) return {-INF,0};
    NODE res=qry(1,1,n,l,r);
    if(rev) res.pos=n-res.pos+1;
	return res;
}

int cnt=0;

i64 calc(int l,int r,char rev){
	NODE n1=qry(l,r,rev),n2,n3;
	i64 res=-INF;
	n2=n1,n3=qry(n1.pos+1,r,rev);
	while(n3.pos){
		++cnt;
		res=std::max(res,n1.max+qry(n2.pos+1,n3.pos-1,rev).max+n3.max);
		n2=n3;
		n3=qry(n2.pos+1,r,rev);
		if(n2.max*2<=n1.max+n3.max){
			res=std::max(res,n1.max+n2.max+n3.max);
			break;
		}
	}
    return res;
}

int main(){
	#ifndef ONLINE_JUDGE
	freopen("d_6_4.in", "r", stdin);
	freopen("name.out", "w", stdout);
	#endif

	int o,l,r,x,q;
	scanf("%d%d",&n,&q);
	read(1,1,n);
	while(q--){
		scanf("%d%d%d",&o,&l,&r);
		if(o==1){
			i64 res=std::max(calc(l,r,0),calc(n-r+1,n-l+1,1));
            if(res<=-INF/2) puts("No");
            else printf("%lld\n",res);
		}else{
			scanf("%d",&x);
			modify(1,1,n,l,r,x);
		}
	}

    return 0;
}