[AdditionalFile176.zip](file://AdditionalFile176.zip?type=additional_file)

#176. 动理序列最值

标签: 传统 | 时间限制: 4000 ms | 内存限制: 256 MiB 通过: 104 | 提交: 195

题目描述

这是一道模板题。

给你两个序列 $K_i$ 和 $B_i$，要求支持在线进行如下操作：

1. 给 $X > 0$，对于每个 $B_i$，变成 $B_i + K_i X$。
2. 给 $L, R, Y$，求出在 $i \in [L, R]$ 中第 $Y$ 大的 $B_i$ 值。
3. 修改一组 $K_i, B_i$。

输入格式

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

接下来一行，输入 $N$ 个整数表示 $K_i$。

接下来一行，输入 $N$ 个整数表示 $B_i$。

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

• 1 X
• 2 L R Y
• 3 i k b

输出格式

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

样例

输入

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% 的数据，保证 $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}$。