思路

除了 C 操作，与P6242 线段树3相同。而对于 C 操作，先把所有值与最小值 $minn$ 进行取 $\min$ 操作，再进行区间修改，加上 $-minn+x$。但是不知道为什么只有 40pts,求大佬帮助。

代码

#include<bits/stdc++.h>
#define int long long
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
using namespace std;
const int N=5e5+5;
int n,m,a[N],minn=INT_MAX;
struct node
{
	int l,r,sum;
	int maxn,maxn_,second,cnt;
	int add1,add1_,add2,add2_;
}tree[N<<2];
void push_up(int x)
{
	tree[x].sum=tree[ls(x)].sum+tree[rs(x)].sum;
	tree[x].maxn_=max(tree[ls(x)].maxn_,tree[rs(x)].maxn_);
	if(tree[ls(x)].maxn==tree[rs(x)].maxn) 
	{
		tree[x].maxn=tree[ls(x)].maxn;
		tree[x].second=max(tree[ls(x)].second,tree[rs(x)].second);
		tree[x].cnt=tree[ls(x)].cnt+tree[rs(x)].cnt;
	} 
	else if(tree[ls(x)].maxn>tree[rs(x)].maxn) 
	{
		tree[x].maxn=tree[ls(x)].maxn;
		tree[x].second=max(tree[ls(x)].second,tree[rs(x)].maxn);
		tree[x].cnt=tree[ls(x)].cnt;
	} 
	else 
	{
		tree[x].maxn=tree[rs(x)].maxn;
		tree[x].second=max(tree[ls(x)].maxn,tree[rs(x)].second);
		tree[x].cnt =tree[rs(x)].cnt;
	}
}
void update(int x,int k1,int k1_,int k2,int k2_) 
{
	tree[x].sum+=k1*tree[x].cnt+k2*(tree[x].r-tree[x].l+1-tree[x].cnt);
	tree[x].maxn_=max(tree[x].maxn_,tree[x].maxn+k1_);
	tree[x].add1_=max(tree[x].add1_,tree[x].add1+k1_);
	tree[x].maxn+=k1,tree[x].add1+=k1;
	tree[x].add2_=max(tree[x].add2_,tree[x].add2+k2_);
	if(tree[x].second!=INT_MIN) 
		tree[x].second+=k2;
	tree[x].add2+=k2;
}
void push_down(int x)
{
	int tt=max(tree[ls(x)].maxn,tree[rs(x)].maxn);
	if(tree[ls(x)].maxn==tt)
		update(ls(x),tree[x].add1,tree[x].add1_,tree[x].add2,tree[x].add2_);
	else 
		update(ls(x),tree[x].add2,tree[x].add2_,tree[x].add2,tree[x].add2_);
	if(tree[rs(x)].maxn==tt)
		update(rs(x),tree[x].add1,tree[x].add1_,tree[x].add2,tree[x].add2_);
	else 
		update(rs(x),tree[x].add2,tree[x].add2_,tree[x].add2,tree[x].add2_);
	tree[x].add1=tree[x].add1_=tree[x].add2=tree[x].add2_=0;
}
void build(int x,int tl,int tr)
{
	tree[x].l=tl,tree[x].r=tr;
	tree[x].add1=tree[x].add1_=tree[x].add2=tree[x].add2_=0;
	if(tl==tr)
	{
		tree[x].sum=tree[x].maxn=tree[x].maxn_=a[tl];
		tree[x].second=INT_MIN,tree[x].cnt=1;
		return;
	}
	int tmid=(tl+tr)>>1;
	build(ls(x),tl,tmid);
	build(rs(x),tmid+1,tr);
	push_up(x);
}
void update1(int x,int l,int r,int k) 
{
	if(tree[x].l>r||tree[x].r<l) 
		return;
	if(l<=tree[x].l&&tree[x].r<=r) 
	{
		update(x,k,k,k,k);
		return;
	}
	push_down(x);
	update1(ls(x),l,r,k),update1(rs(x),l,r,k);
	push_up(x);
}
void update2(int x,int l, int r, int k) 
{
	if(tree[x].l>r||tree[x].r<l||k>=tree[x].maxn) 
		return;
	if(l<=tree[x].l&&tree[x].r<=r&&k>tree[x].second) 
	{
		update(x,k-tree[x].maxn,k-tree[x].maxn,0,0);
		return;
	}
	push_down(x);
	update2(ls(x),l,r,k),update2(rs(x),l,r,k);
	push_up(x);
}
int query2(int x,int l,int r) 
{
	if(tree[x].l>r||tree[x].r<l) 
		return INT_MIN;
	if(l<=tree[x].l&&tree[x].r<=r) 
		return tree[x].maxn;
	push_down(x);
	return max(query2(ls(x),l,r),query2(rs(x),l,r));
}
int query3(int x,int l,int r) 
{
	if(tree[x].l>r||tree[x].r<l) 
		return INT_MIN;
	if(l<=tree[x].l&&tree[x].r<=r) 
		return tree[x].maxn_;
	push_down(x);
	return max(query3(ls(x),l,r),query3(rs(x),l,r));
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i],minn=min(minn,a[i]);
	build(1,1,n);
	cin>>m;
	while(m--)
	{
		char opt;
		int l,r,x;
		cin>>opt>>l>>r;
		if(opt=='P'||opt=='C')
			cin>>x;
		if(opt=='C')
		{
			update2(1,l,r,minn);
			update1(1,l,r,-minn+x);
		}
		else if(opt=='P')
			update1(1,l,r,x),minn=min(minn,x);
		else if(opt=='Q')
			cout<<query2(1,l,r)<<"\n";
		else if(opt=='A')
			cout<<query3(1,l,r)<<"\n";
	}
	return 0;
}