传统题 1000ms 256MiB

南师大奇谈

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Problem:南师大奇谈

时间限制:1s

空间限制:2,000,000KiB

Background && Description

​ 原力清理大师到最后也没等来你的帮助,气喘吁吁爬~~(字面意思)上了楼顶。但是直到此刻,当原力清理大师站在楼顶享受烈日曝晒~~校园的美丽风景时,才明白美丽大方的wq老师的良苦用心。要想看得更远,不妨先站在巨人的肩膀上。

​ 为此,原力清理大师来到了学校的后山。奇妙的是,在这里他碰到了南师大的山神。山神将南师大后山排成一列,绵延不绝。山神告诉原力清理大师,现在南师大共有 nn 座山,每座山的高度是 aia_i

​ 现在,山神将询问原力清理大师将某座山增高之后的影响,共询问 qq 次。假设原力清理大师此时正处于第 ii 座山,他向右看去,第一个高度超过(不包括一样高)他当前所在的山的山视为挡住他的视线,且无论后面的山有多高,都视为该山挡住他的视线。若山神此时将两座山之间的某一座山的高度增加 hh ,使其挡住原力清理大师的视线,则视为这座山对第 ii 座山产生影响

​ 现在,原力清理大师的脑子因为熬夜已经彻底生锈了。虽然你上一次无情地鸽掉了他的提问,但是迫于无奈,他不得不再次死皮赖脸地向你请教这 qq 次询问的答案。

Input Format

​ 第一行为一个整数 nn ,代表南师大此刻山的数量。

​ 第二行为 nn 个正整数,每个数代表第 i(1qiqn)i (1 \le qi \le qn) 座山的高度 aia_i

​ 第三行为一个正整数 qq ,代表山神向原力清理大师询问的次数。

​ 接下来 qq 行,每行两个正整数,分别代表山神想要将第 ii 座山的高度增加 hih_i

Output Format

输出 qq 行,每行一个整数,代表山神若增高了某座山,会产生影响的山的数量 。

Data Range

  • 对于 5050% 的数据,1n10001 \leq n\leq 1000 ;对于 100100% 的数据, 1n1000001 \leq n\leq 100000
  • 对于 5050% 的数据,1q10001 \leq q\leq 1000 ;对于 100100% 的数据, 1q1000001 \leq q\leq 100000
  • 对于 100100% 的数据, 1qn1 \leq q\leq n ;对于 5050% 的数据,1h100000001 \leq h\leq 10000000 ;对于 100100% 的数据, 1h1000001 \leq h\leq 100000
  • q次询问独立,互不影响。

Input Example #1:

6
1 4 2 8 5 7
2
5 4
2 3

Output Example #1:

1
0

Example Explanation:

​ 第五座山增高后超过了第四座山,对其产生了影响;第二座山无论增高多少,都比第一座山高,不产生影响。

Attention:Attention: 山神只是想想,不是真的要把山增高哟。

2024年暑假算法队集训赛2

未参加
状态
已结束
规则
IOI
题目
14
开始于
2024-7-22 12:00
结束于
2024-7-24 12:00
持续时间
48 小时
主持人
参赛人数
19