传统题 700ms 256MiB

数列分块 2

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

给出一个长为 nn 的数列,以及 nn 个操作,操作涉及区间加法,询问区间内小于某个值 c2c^2 的元素个数。

输入格式

第一行输入一个数字 nn

第二行输入 nn 个数字,第 ii 个数字为 aia_i,以空格隔开。

接下来输入 nn 行询问,每行输入四个数字 opt\mathrm{opt}llrrcc,以空格隔开。

opt=0\mathrm{opt} = 0,表示将位于 [l,r][l, r] 的之间的数字都加 cc

opt=1\mathrm{opt} = 1,表示询问 [l,r][l, r] 中,小于 c2c^2 的数字的个数。

输出格式

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

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

数据范围与提示

对于 100% 100\% 的数据,1n50000,231others 1 \leq n \leq 50000, -2^{31} \leq \mathrm{others}ans2311 \mathrm{ans} \leq 2^{31}-1

20230316分块

未认领
状态
已结束
题目
9
开始时间
2023-3-16 0:00
截止时间
2024-3-16 23:59
可延期
2736 小时