#1978. 上帝之手

    ID: 1978 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>CTT赛事:contest39来源:qoj.ac数据:公开样例线段树

上帝之手

上帝之手

题目描述

标题: 上帝之手 - Problem - QOJ.ac

#4258. 上帝之手

Statistics

The problem was used in the following contests:

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

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

  1. 给定 a,b 和 k,对于所有的 c 满足 a≤c≤b,让世界以 lc−1 的初始混乱度从第 c 天开始发展,把第 b 天的混乱度 xb 写在一张纸上。你只需告诉上帝纸上第 k 大的 xb 即可。保证 1≤a≤b≤n,且 1≤k≤b−a+1。
  2. 给定 a,b 和 x0,对于所有的 c 满足 a≤c≤b,让世界以 x0 的初始混乱度从第 c 天开始发展,把第 b 天的混乱度 xb 写在一张纸上。你只需告诉上帝纸上最大的 xb 即可。(注意:x0 可能大于 lc−1)。保证 1≤a≤b≤n。
  3. 给定 a 和 b,对于所有的 c 满足 a≤c≤b,让世界以 lc−1 的初始混乱度从第 c 天开始发展,把第 b 天的混乱度 xb 写在一张纸上。你只需告诉上帝纸上有多少种不同的 xb 即可。保证 1≤a≤b≤n。

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

输入格式

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

第二行为 n 个非负整数 d1,…,dn。

第三行为 n+1 个非负整数 l0,…,ln。含义见问题描述。

第四行起的 m 行,每行第一个整数 type 表示操作种类。

若 type=0,则后面跟有两个整数 u 和 x,表示将 lu 改为 x。保证 0≤u≤n。

若 type>0,则 type 等于题目描述中对应的测试种类编号。type=1 时后面跟有三个整数 a,b 和 k;type=2 时后面跟有三个整数 a,b 和 x0;type=3 时后面跟有两个整数 a 和 b。具体含义见问题描述。

输出格式

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

样例一

input

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


output

5
1
2
8


限制与约定

对于前 10% 的数据,n,m≤100;

对于前 20% 的数据,n,m≤5000;

对于另 10% 的数据,type≤1;

对于另 20% 的数据,type≤2;

对于另 15% 的数据,type=0 或 3;

对于 100% 的数据,n≤105,m≤2×105,0≤di≤104,0≤li≤109。第二类测试操作中 0≤x0≤109,修改操作中 0≤x≤109。

**时间限制:**2s

**空间限制:**256MB

来源

中国国家集训队互测2015 - By 陈思禹

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

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