如题。

提交记录

#include "bits/stdc++.h"
#define int long long
#define N 500010
using namespace std ;
const int inf = (int)1e12 ;
int a[N] , b[N] ;
struct data{
	int maxa , maxakbj , minb , maxaibj , ans ;
}t[N * 4];
data merge(data A , data B) {
	data C ;
	C.maxa = max(A.maxa , B.maxa) ;
	C.minb = min(A.minb , B.minb) ;
	C.maxakbj = max(A.maxakbj , max(B.maxakbj , B.maxa - A.minb)) ;
	C.maxaibj = max(A.maxaibj , max(B.maxaibj , A.maxa - B.minb)) ;
	C.ans = max(A.ans , max(B.maxa + A.maxaibj , max(A.maxa + B.maxakbj , B.ans))) ;
	return C ;
}
void build(int cur , int l , int r) {
	if(l == r) {
		t[cur].maxa = a[l] ;
		t[cur].minb = b[l] ;
	}
	else {
		int mid = (l + r) / 2 ;
		build(2 * cur , l , mid) ;
		build(2 * cur + 1 , mid + 1 , r) ;
		t[cur] = merge(t[2 * cur] , t[2 * cur + 1]) ;
	}
}
void modify(int cur , int l , int r , int x) {
	if(l == r) {
		t[cur].maxa = a[l] ;
		t[cur].minb = b[l] ;
	}
	else {
		int mid = (l + r) / 2 ;
		if(x > mid) {
			modify(2 * cur + 1 , mid + 1 , r , x) ;
		}
		else {
			modify(2 * cur , l , mid , x) ;
		}
		t[cur] = merge(t[cur * 2] , t[cur * 2 + 1]) ;
	}
}
data find(int cur , int l , int r , int x , int y) {
	if(l == x && r == y) {
		return t[cur] ;
	}
	int mid = (l + r) / 2 ;
	data tot ;
	if(x > mid) {
		tot = find(2 * cur + 1 , mid + 1 , r , x , y) ;
	}
	else if(y > mid) {
		data ans1 = find(2 * cur , l , mid , x , mid) ;
		data ans2 = find(2 * cur + 1 , mid + 1 , r , mid + 1 , y) ;
		tot = merge(ans1 , ans2) ;
	}
	else {
		tot = find(2 * cur , l , mid , x , y) ;
	}
	return tot ;
}
signed main() {
	int n , m ;
	scanf("%lld%lld" , &n , &m) ;
	for(int i = 1 ; i <= n ; i++) {
		scanf("%lld" , &a[i]) ;
	}
	for(int i = 1 ; i <= n ; i++) {
		scanf("%lld" , &b[i]) ;
	}
	build(1 , 1 , n) ;
	while(m--) {
		int id , x , y ;
		scanf("%lld%lld%lld" , &id , &x , &y) ;
		if(id == 1) {
			a[x] = y ;
			modify(1 , 1 , n , x) ;
		}
		else if(id == 2) {
			b[x] = y ;
			modify(1 , 1 , n , x) ;
		}
		else {
			data qwq = find(1 , 1 , n , x , y) ;
			printf("%lld\n" , qwq.ans) ;
		}
	}
	return 0 ;
}