我做法跟正解不大一样，思路如下：

假设当前在第 $i$ 个位置做到了一次取 $\max$ 操作，在这次操作之后第 $i$ 个位置上又加上的数的和为 $s_i$。分类讨论：

因为一定有解，所以 $a_i\le a'_i-s_i$（和同学讨论后怀疑这里可能不一定），且有 $\max(a_i,x)\le a'_i-s_i$。

若 $a_i=a'_i-s_i$，那么当前操作就有 $x\le a_i$，即 $x\le a'_i-s_i$。

若 $a_i<a'_i-s_i$，那么当前操作就有 $x\le a'_i-s_i$。

所以每次求得的 $x$ 都满足 $x\le \min_{i=l}^r{(a'_i-s_i)}$。

那么直接用线段树维护 $a'_i-s_i$，然后顺序操作，区间加直接加，求 $x$ 直接求区间 $\min$。

交上去 #5 AC，只有 10pts。代码：

#include<bits/stdc++.h>
using namespace std;
#define N 100003
#define LL long long
#define INF 0x3f3f3f3f
int T,n,q;
LL a[N],b[N];
struct opti{
	int op,l,r;
	LL x;
}p[N];
struct node{
	int l,r,mn,lz;
}t[N*4];
void build(int l,int r,int p){
	t[p].l=l,t[p].r=r;
	if(l==r){
		t[p].mn=b[l],t[p].lz=0;
		return;
	}
	int mid=l+r>>1;
	build(l,mid,p*2),build(mid+1,r,p*2+1);
	t[p].mn=min(t[p*2].mn,t[p*2+1].mn);
}
int lth(node p){return p.r-p.l+1;}
void psd(int p){
	int ls=p*2,rs=p*2+1;
	t[ls].mn+=t[p].lz,t[rs].mn+=t[p].lz;
	t[ls].lz+=t[p].lz,t[rs].lz+=t[p].lz;
	t[p].lz=0;
}
void add(int l,int r,LL a,int p){
	if(t[p].r<l||t[p].l>r) return;
	if(t[p].l>=l&&t[p].r<=r){
		t[p].mn+=a,t[p].lz+=a;
		return;
	}
	if(t[p].lz) psd(p);
	add(l,r,a,p*2),add(l,r,a,p*2+1);
	t[p].mn=min(t[p*2].mn,t[p*2+1].mn);
}
LL camn(int l,int r,int p){
	if(t[p].r<l||t[p].l>r) return INF;
	if(t[p].l>=l&&t[p].r<=r)
		return t[p].mn;
	return min(camn(l,r,p*2),camn(l,r,p*2+1));
}
int main(){
	scanf("%d",&T);
	while(T--){
		scanf("%d%d",&n,&q);
		for(int i=1;i<=n;++i)
			scanf("%lld",&a[i]);
		for(int i=1;i<=q;++i){
			scanf("%d%d%d",&p[i].op,&p[i].l,&p[i].r);
			if(p[i].op==1) scanf("%lld",&p[i].x);
		}
		for(int i=1;i<=n;++i)
			scanf("%lld",&b[i]);
		build(1,n,1);
		for(int i=1;i<=q;++i) //将所有加数减掉以维护a'_i-s_i
			if(p[i].op==1) add(p[i].l,p[i].r,-p[i].x,1);
		for(int i=1;i<=q;++i)
			if(p[i].op==1) add(p[i].l,p[i].r,p[i].x,1);
			else printf("%lld ",camn(p[i].l,p[i].r,1));
		puts("");
	}
	return 0;
}