#P7706. 「Wdsr-2.7」文文的摄影布置

「Wdsr-2.7」文文的摄影布置

题目背景

作为幻想乡知名的记者射命丸文,文文常常需要为文文新闻采集相关的照片素材。

具体而言,文文会采集一大串的图片,用于为新的一期报纸提供图片。作为一份简短的快报,文文会从素材库中使用三张图片,第一张放在开头,第三张放在结尾,用于激发读者的阅读兴趣(毕竟,报纸的开头和结尾是最容易被看到的);第二张,则是为了帮助读者理解相关内容。

可是作为无双风神,文文收集的照片实在是太多了,以至于一时半会儿处理不过来。按照惯例,文文找到了在一旁吃瓜的你,希望你能帮她解决困难。

题目描述

尽管图片非常多,但幸运的是,文文已经将它们排成了一列,从左到右分别编号为 1n1 \sim n,文文选取的三张图片,应该是一个长度为 3\bf 3 的子序列。(不妨设选取的照片的序号为 i,j,ki,j,k ,则必须要有 i<j<ki<j<k )。

此外,文文给每张照片定了一个吸引度 AiA_i大小 BiB_i

因为报纸版面太大会降低读者的兴趣,于是选定两张照片 i,ki,k 后,规定必须选择最小的 BjB_j

形式化地说,规定 ψ(i,k)=Ai+Akmin(Bj)\psi(i,k) = A_i + A_k - \min(B_j),其中需要满足 i<j<ki < j < k

摸清了照片价值的计算,文文会告诉你共 mm 个操作,可以分为以下三种:

  • 1 x y\colorbox{f0f0f0}{\verb!1 x y!} :照片的吸引度发生变化。文文要将 AxA_x 修改为 yy

  • 2 x y\colorbox{f0f0f0}{\verb!2 x y!} :照片的大小发生变化。文文要将 BxB_x 修改为 yy

  • 3 l r\colorbox{f0f0f0}{\verb!3 l r!} :文文打算利用素材库的第 ll 到第 rr 张中的图片,你要告诉她 ψ(x,y)\psi(x,y)最大值lxx+1<yrl\le x\le x+1<y \le r )。

输入格式

第一行两个整数 n,mn,m,分别表示照片数量和操作次数。

第二行 nn 个整数,表示序列 AA,描述每张照片的吸引度。

第三行 nn 个整数,表示序列 BB,描述每张照片的大小。

接下来 mm 行,每行描述一个操作,格式如上所述。

输出格式

对于每个操作三,输出一行一个整数,表示答案。

6 6
1 4 2 3 5 6
5 3 4 1 6 7
3 2 5
3 1 6
1 2 3
3 1 6
2 6 1
3 1 6
8
9
8
8

提示

数据范围及约定

$$\def{\arraystretch}{1.5}\begin{array}{|c|c|c|c|}\hline \textbf{Subtask} & \bm{n,m} & \textbf{特殊性质} & \textbf{分值}\cr\hline 1 & 1\le n,m\le 300 & \text{无} & 10\cr\hline 2 & 1\le n,m\le 5\times 10^3 & \text{无} & 20\cr\hline 3 & 1\le n,m\le 5\times 10^5 & \text{仅有操作 3} & 20\cr\hline 4 & 1\le n,m\le 10^5 & \text{无} & 20\cr\hline 5 & \text{无特殊限制} & \text{无} & 30\cr\hline \end{array}$$
  • 对于 100%100\% 的数据:

    1n,m5×1051 \le n,m \le 5 \times 10^5

    1Ai,Bi,y1081 \leq A_i,B_i,y \leq 10^81xn1 \le x \le n1lrn1 \le l \le r \le n

    保证 rl+13r-l+1 \geq 3,即询问的区间长度大于等于 33