上帝之手

时间限制:20s      空间限制:256MB

题目描述

上帝之手操纵着四维空间。假设四维空间中上帝关心的部分共N天,定义第i天结束时一个三维世界的混乱度为Xi。由于一些自然的原因,第i天该世界的混乱度会增加Di,即Xi=Xi-1+Di。但为了世界的平衡,每天该世界都有一个混乱度的上限值Li,即实际上Xi=min{Xi-1+Di , Li}。
上帝想对该四维空间作一系列测试,于是希望你帮忙建立一个模型。具体有以下三种测试:
(1)给定A、B和K,要求找到一个C(A<=C<=B),使得世界以LC-1的初始混乱度从第C天开始发展将得到第K大的XB­。你只需告诉上帝第K大的XB值即可。
(2)给定A、B和X0,要求找到一个C(A<=C<=B),使得世界以X0的初始混乱度从第C天开始发展将得到最大的XB。你只需告诉上帝最大的XB值即可(注意:X0可能大于LC-1)。
(3)给定A和B,要求对于所有满足A<=C<=B 的C,求出世界以LC-1的初始混乱度从第C天开始发展将得到的XB的不同值的种数­。
当然,上帝还会根据测试的结果修改某些位置的Li。你能成功帮助上帝完成测试吗?


输入格式

第一行包含两个正整数N和M,按序表示总天数和总操作(包含测试和修改)次数。
第二行为N个非负整数 D1-DN,第三行为N+1个非负整数L0-LN。含义见问题描述。
第四行起的M行,每行第一个整数type表示操作种类。
若type=0,则后面跟有两个整数u和x,表示将Lu改为x。
若type>0,则type等于题目描述中对应的测试种类编号。type=1时后面跟有三个整数A、B和K;type=2时后面跟有三个整数A、B和X0;type=3时后面跟有两个整数A和B。具体含义见问题描述。


输出格式

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


样例输入

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

提示

对于100%的数据,N<=10^5,M<=2×10^5,0<=Di<=10^4,0<=Li, X0, x<=10^9,0<=u<=N,1<=A<=B<=N,1<=K<=B-A+1。


题目来源

2015年集训队互测

Menuappsclose