JZTXT

P7706 文文的摄影布置

发布时间 2023-03-24 08:03:18作者: lsty

P7706 文文的摄影布置

给你两个长度为 \(n\) 的序列 \(A\) 和 \(B\)，每次询问需要支持在一个区间内选出两个点 \(i\) 和 \(k\) 令 \(A_i + A_k - \min_{j=i+1}^{k-1}B_j\) 最大，保证每次询问区间长度在 \(3\) 以上，需要支持对 \(A\) 和 \(B\) 序列的单点修改

把三个东西都放在同一个区间内是困难的，因为这几个位置之间是相互影响的，把 \(k\) 挪后或者 \(i\) 挪前可能换来更小的 \(B_j\)

那这里有一个套路，就是把这三个东西划分到两个无交的东西里面去做，防止在同一个区间里面相互影响

类似树分治，我们把一个区间答案划分为三种，

  1. 横跨区间中点
  2. 在左子区间
  3. 在右子区间

左右子区间的情况递归一下就能解决，考虑怎么解决第一种

假设已经有了 \([l,mid]\) 的 \(A_i-B_j\) 的最大值，那 \(A_k\) 直接在 \([mid+1,r]\) 里面的最大值

反之有了 \([mid+1,r]\) 的 \(A_k-B_j\) 的最大值，那 \(A_i\) 直接在 \([l,mid]\) 里面取一个最大值

然后发现计算 \(A_i-B_j\) 和 \(A_k-B_j\) 的做法再用一次上面的方法，也这样划分就可以了

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;
typedef long long ll;
const int N = 5e5 + 10, inf = 0x3f3f3f3f;
ll a[N], b[N];
int n, m;

struct node{
	int l, r;
	ll lmax, rmax;
	ll amax, bmin;
	ll ans;
	node(){
		l = r = 0;
		lmax = -inf, rmax = -inf;
		ans = -inf;
	}
}tr[N << 2];

void pushup(node& root, const node& ls, const node& rs){
	root.amax = max(ls.amax, rs.amax);
	root.bmin = min(ls.bmin, rs.bmin);
	root.lmax = ls.amax - rs.bmin;
	root.rmax = rs.amax - ls.bmin;
	root.lmax = max(root.lmax, max(ls.lmax, rs.lmax));
	root.rmax = max(root.rmax, max(ls.rmax, rs.rmax));
	root.ans = max(max(ls.lmax + rs.amax, rs.rmax + ls.amax), max(ls.ans, rs.ans));
}

void build(int u, int l, int r){
	tr[u].l = l, tr[u].r = r;
	if(l == r){
		tr[u].amax = a[l];
		tr[u].bmin = b[l];
		tr[u].lmax = -inf;
		tr[u].rmax = -inf;
		tr[u].ans = -inf;
		return ;
	}
	int mid = l + r >> 1;
	build(u << 1, l, mid);
	build(u << 1 | 1, mid + 1, r);
	pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}

void modify(int u, int x, int v, int type){
	if(tr[u].l == x && tr[u].r == x){
		if(type == 0)
			tr[u].amax = v;
		else
			tr[u].bmin = v;
		return ;
	}
	int mid = tr[u].l + tr[u].r >> 1;
	if(x <= mid)
		modify(u << 1, x, v, type);
	else
		modify(u << 1 | 1, x, v, type);
	pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}

node query(int u, int l, int r){
	if(l <= tr[u].l && tr[u].r <= r){
		return tr[u];
	}
	int mid = tr[u].l + tr[u].r >> 1;
	if(r <= mid)	return query(u << 1, l, r);
	else if(l > mid)	return query(u << 1 | 1, l, r);
	else{
		node res;
		node ls = query(u << 1, l, r);
		node rs = query(u << 1 | 1, l, r);
		pushup(res, ls, rs);
		return res;
	}
}

int main(){
	scanf("%d%d", &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);
	
	for(int i = 1; i <= m; i++){
		int op, x, y;
		scanf("%d%d%d", &op, &x, &y);
		if(op == 1)
			modify(1, x, y, 0);
		else if(op == 2)
			modify(1, x, y, 1);
		else{
			node res = query(1, x, y);
			printf("%lld\n", res.ans);
		}
	}
	return 0;
}