#1611. 动理序列最值

动理序列最值

题目描述

这是一道模板题。

给你两个序列 KiK_iBiB_i,要求支持在线进行如下操作:

  1. X>0X > 0,对于每个 BiB_i,变成 Bi+KiXB_i + K_iX

  2. L,R,YL, R, Y,求出在 i[L,R]i \in [L, R] 中第 YY 大的 BiB_i 值。

  3. 修改一组 Ki,BiK_i, B_i

输入格式

第一行输入两个正整数 N,QN, Q

接下来一行,输入 NN 个整数表示 KiK_i

接下来一行,输入 NN 个整数表示 BiB_i

接下来共 QQ 行,每行首先输入一个整数表示操作编号,分别有以下三种情况:

  • 1 X1\ X
  • 2 L R Y2\ L\ R\ Y
  • 3 i k b3\ i\ k\ b

输出格式

对于每个 22 询问,输出一个整数表示答案。

样例

3 10
-1 3 1
1 -3 0
2 1 3 1
2 1 3 2
2 1 3 3
1 1
2 1 3 1
2 1 3 2
2 1 3 3
3 2 0 2
2 2 3 1
2 2 3 2
1
0
-3
1
0
0
2
1

数据范围与提示

对于 100%100\% 的数据,保证 $1\le N, Q\le 2\times 10^5; 1\le Y \le \min(R - L + 1, 30); X, |K_i| \le 10^6, |B_i| \le 10^{18}$。