#P11733. [集训队互测 2015] 上帝之手

[集训队互测 2015] 上帝之手

题目描述

上帝之手操纵着四维空间。假设四维空间中上帝关心的部分共 nn 天,定义第 ii 天结束时一个三维世界的混乱度为 xix_i。由于一些自然的原因,第 ii 天该世界的混乱度会增加 did_i,但为了世界的平衡,每天该世界都有一个混乱度的上限值 lil_i,即实际上 xi=min{xi1+di,li}x_i = \min\{x_{i-1}+d_i , l_i\}

上帝想对该四维空间作一系列测试,于是希望你帮忙建立一个模型。具体有以下三种测试:

  1. 给定 a,ba, bkk,对于所有的 cc 满足 acba \leq c \leq b,让世界以 lc1l_{c-1} 的初始混乱度从第 cc 天开始发展,把第 bb 天的混乱度 xbx_b 写在一张纸上。你只需告诉上帝纸上第 kk 大的 xbx_b 即可。保证 1abn1 \leq a \leq b \leq n,且 1kba+11 \leq k \leq b - a + 1
  2. 给定 a,ba, bx0x_0,对于所有的 cc 满足 acba \leq c \leq b,让世界以 x0x_0 的初始混乱度从第 cc 天开始发展,把第 bb 天的混乱度 xbx_b 写在一张纸上。你只需告诉上帝纸上最大的 xbx_b 即可。(注意:x0x_0 可能大于 lc1l_{c-1})。保证 1abn1 \leq a \leq b \leq n
  3. 给定 aabb,对于所有的 cc 满足 acba \leq c \leq b,让世界以 lc1l_{c-1} 的初始混乱度从第 cc 天开始发展,把第 bb 天的混乱度 xbx_b 写在一张纸上。你只需告诉上帝纸上有多少种不同的 xbx_b 即可。保证 1abn1 \leq a \leq b \leq n

当然,上帝还会修改某些位置的 lil_i。你能成功帮助上帝完成测试吗?

输入格式

第一行包含两个正整数 nnmm,分别表示总天数和总操作(包含测试和修改)次数。

第二行为 nn 个非负整数 d1,,dnd_1, \dots, d_n

第三行为 n+1n+1 个非负整数 l0,,lnl_0, \dots, l_n。含义见问题描述。

第四行起的 mm 行,每行第一个整数 type\mathrm{type} 表示操作种类。

type=0\mathrm{type}=0,则后面跟有两个整数 uuxx,表示将 lul_u 改为 xx。保证 0un0 \leq u \leq n

type>0\mathrm{type}>0,则 type\mathrm{type} 等于题目描述中对应的测试种类编号。type=1\mathrm{type} = 1 时后面跟有三个整数 a,ba, bkktype=2\mathrm{type} = 2 时后面跟有三个整数 a,ba, bx0x_0type=3\mathrm{type} = 3 时后面跟有两个整数 aabb。具体含义见问题描述。

输出格式

对于每个测试输出一行,包含一个整数表示测试结果。

3 5
2 1 3
2 6 7 5
1 1 2 2
3 1 3
0 3 15
3 1 3
2 1 3 2
5
1
2
8

提示

  • 对于前 10%10\% 的数据,n,m100n, m \leq 100
  • 对于前 20%20\% 的数据,n,m5000n, m \leq 5000
  • 对于另 10%10\% 的数据,type1\mathrm{type} \leq 1
  • 对于另 20%20\% 的数据,type2\mathrm{type} \leq 2
  • 对于另 15%15\% 的数据,type=0\mathrm{type} = 033
  • 对于 100%100\% 的数据,n105n \leq 10^5m2×105m \leq 2 \times 10^50di1040 \leq d_i \leq 10^40li1090 \leq l_i \leq 10^9。第二类测试操作中 0x01090 \leq x_0 \leq 10^9,修改操作中 0x1090 \leq x \leq 10^9