#P9744. LJJ 的农场

    ID: 6370 传统题 3000ms 512MiB 尝试: 2 已通过: 2 难度: 8 上传者: 标签>CF2400提高+/省选-逆向还原操作根号分块凸包单调栈二分查找

LJJ 的农场

题目描述

有一个 m×mm\times m 网格和两个长度为 mm 的整数数组 a,ba,b。第 ii 行第 jj 列的值为 aij+bjia_i j+b_j i。

有 nn 次操作。每次给定 op,x,sop,x,s。若 op=0op=0,将 axa_x 增加 ss。若 op=1op=1,将 bxb_x 增加 ss。求操作前和每次操作后,网格中所有值的最小值。

输入格式

第一行两个整数 n,mn,m。第二、三行各 mm 个整数,分别为数组 aa 和 bb。

接下来 nn 行,每行三个整数 opi,xi,siop_i,x_i,s_i,描述一次操作。

输出格式

输出 n+1n+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≤1000000\le n\le100000,1≤m≤1000001\le m\le100000,初始数组元素满足 −231≤ai,bi≤231−1-2^{31}\le a_i,b_i\le2^{31}-1。opi∈{0,1}op_i\in\{0,1\},1≤xi≤m1\le x_i\le m,0≤si≤50000\le s_i\le5000。

测试点 附加条件
1–2 n,m≤1000n,m\le1000
3–5 n≤100000, m≤1000n\le100000,\ m\le1000
6 n=0n=0
7–10 无

原稿给出的初始值范围是 −5×108<ai,bi<5×108-5\times10^8<a_i,b_i<5\times10^8。本站现有评测含有更小的初始值,因此本页采用有符号 32 位整数范围。累加后的数组元素和格子值请用 64 位整数保存。

原题面 PDF