【模板】数列分块入门 3

【模板】数列分块入门 3

作业已超过截止时间,您无法递交本题目。

描述

给出一个长为\(n\)的数列,以及\(n\)个操作,操作涉及区间加法,询问区间内小于某个值\(x\)的前驱(比其小的最大元素)。

格式

输入格式

第一行输入一个数字\(n\)。

第二行输入\(n\)个数字,第\(i\)个数字为\(a_i\),以空格隔开。

接下来输入\(n\)行询问,每行输入四个数字\(opt、l、r、c\),以空格隔开。

若\(opt=0\),表示将位于\([l,r]\)的之间的数字都加\(c\)。

若\(opt=1\),表示询问\([l,r]\)中,中\(c\)的前驱的值,不存在则输出\(-1\)。

输出格式

对于每次询问,输出一行一个数字表示答案。

样例1

输入样例1

4
1 2 2 3
0 1 3 1
1 1 4 4
0 1 2 2
1 1 2 4

输出样例1

3
-1

限制

对于\(100\%\)的数据,\(1≤n100000,-2^{31}≤others、ans≤2^{31}-1\)。

数列分块入门

未认领
状态
已结束
题目
4
开始时间
2022-09-12 00:00
截止时间
2022-09-19 23:59
可延期
504.0 小时