题目描述
有一个 m×m 网格和两个长度为 m 的整数数组 a,b。第 i 行第 j 列的值为 aij+bji。
有 n 次操作。每次给定 op,x,s。若 op=0,将 ax 增加 s。若 op=1,将 bx 增加 s。求操作前和每次操作后,网格中所有值的最小值。
输入格式
第一行两个整数 n,m。第二、三行各 m 个整数,分别为数组 a 和 b。
接下来 n 行,每行三个整数 opi,xi,si,描述一次操作。
输出格式
输出 n+1 行,每行一个整数。首行为初始答案,其余各行为相应操作后的答案。
样例
4 3
3 2 1
3 2 1
0 1 3
0 3 1
1 2 3
0 2 2
6
6
8
8
9
数据范围
0≤n≤100000,1≤m≤100000,初始数组元素满足 −231≤ai,bi≤231−1。opi∈{0,1},1≤xi≤m,0≤si≤5000。
| 测试点 |
附加条件 |
| 1–2 |
n,m≤1000 |
| 3–5 |
n≤100000, m≤1000 |
| 6 |
n=0 |
| 7–10 |
无 |
原稿给出的初始值范围是 −5×108<ai,bi<5×108。本站现有评测含有更小的初始值,因此本页采用有符号 32 位整数范围。累加后的数组元素和格子值请用 64 位整数保存。
原题面 PDF