#P13095. [FJCPC 2025] 炒股高手

[FJCPC 2025] 炒股高手

题目描述

小 A 立志成为一名炒股高手。经过长时间的学习,他自信已掌握了丰富的理论知识,并精心挑选出了一支股票,决定在接下来的 nn 个交易日内进行实战操作。

股票之神向小 A 投来了注视,他帮你预知了接下来 nn 个交易日中这只股票的股价。由于股票之神擅长数学,所有价格均以自然对数的形式给出。也就是说,在第 ii 天(1in1 \leq i \leq n),会得到一个正整数 aia_i,表示当天该股票的价格为 eaie^{a_i} 元。需要注意的是,在本题中,小 A 可以购买非整数份的股票。

由于手头资金有限,小 A 决定公开向他人借款,称为"鸡债"。为了方便管理和收益核算,他规定每位出借人均提供固定的 eke^k 元借款。

在这 nn 天内,共有 mm 位出借人愿意向小 A 提供鸡债。

对于第 ii 位出借人,他会在第 sis_i 天开盘前向小 A 提供 eke^k 元,在第 tit_i 天收盘后要求结算收益。在这段时间内,小 A 可自由使用这笔资金进行任意次数的买入与卖出操作。

你的任务是:对于每一笔鸡债,计算小 A 在最优操作下所能获得的最终总资产(即本金加收益)的自然对数值 kk,并输出该整数。 换句话说,若小 A 最终通过操作将手中 eke^k 元变为 ewe^w 元,则你应输出该整数 ww

输入格式

第一行包含两个正整数 nn1n1051 \leq n \leq 10^5) 和 mm1m1051 \leq m \leq 10^5),分别表示交易日的数量以及鸡债的数量。

第二行包含 nn 个正整数 a1,a2,,ana_1, a_2, \dots, a_n1ai1041 \leq a_i \leq 10^4),其中第 ii 天的股票价格为eaie^{a_i}

第三行包含一个正整数 kk1k1091 \leq k \leq 10^9),表示每份鸡债提供的借款金额为eke^k

接下来 mm 行,每行包含两个整数 sis_itit_i1sitin1 \leq s_i \leq t_i \leq n),表示第 ii 份鸡债的借款开始日和收益结算日。

输出格式

输出共 mm 行,每行一个正整数 wiw_i,表示第 ii 份鸡债的本金加收益总额为 ewie^{w_i} 元。

6 2
3 2 4 5 3 6
2
2 4
3 6
5
6

提示

在样例中,一共有 66 个交易日,22 份鸡债。

每天的股价为 e3,e2,e4,e5,e3,e6e^3, e^2, e^4, e^5, e^3, e^6

鸡债的本金均为 e2e^2

11 份鸡债:第 22 天借出,在第 44 天归还。

22 份鸡债:第 33 天借出,在第 66 天归还。

对于第 11 份鸡债:三天的股价为 [e2,e4,e5][e^2, e^4, e^5] ,最优方案为第 22 天买入,第 44 天卖出。最终资产为 e2÷e2×e5=e5e^2 \div e^2 \times e^5 = e^5

输出答案为 55

对于第 22 份鸡债:四天的股价为 [e4,e5,e3,e6][e^4, e^5, e^3, e^6] ,最优方案为第 33 天买入,第 44 天卖出,第 55 天再买入,第 66 天再卖出。最终资产为 e2÷e4×e5÷e3×e6=e6e^2 \div e^4 \times e^5 \div e^3 \times e ^6 = e^6

输出答案为 66