题目背景
JOISC2022 D4T2
题目描述
JOI 君有 N 条鱼,编号为 1,2,…,N。第 i (1≤i≤N) 条鱼的大小为 Ai。
当我们养鱼的时候,需要注意如下的一个事实:如果有两条鱼离得很近,那么随着时间的流逝,可能会有其中一条吃掉另一条。其中,两条鱼离得很近,当且仅当它们中间没有鱼。
更具体地,如果鱼 x 的大小不小于鱼 y 的大小,且鱼 x,y 离得很近,那么 x 可以吃掉 y,且 x 的大小变为原来 x,y 的大小之和。如果 x,y 一样大,那么 x 吃掉 y 或 y 吃掉 x 都可能发生。
JOI 君会养 Q 天鱼。为了消磨时光,他会进行如下的思想实验。在第 j 天 (1≤j≤Q),JOI 君会进行如下行动中的一个:
-
第一类:JOI 君给鱼 Xj 吃了某些秘制的食物。这会将鱼 Xj 的大小变为 Yj。
-
第二类:JOI 君将编号在区间 [Lj,Rj] 内的鱼单独拿出来,并进行以下实验:
JOI 君将鱼 Lj,Lj+1,…,Rj 从左到右依次放在一个鱼缸中。由于鱼们具有如上所述的特点,最后只有一条鱼会存活。存活的这条鱼的编号取决于在哪些时刻哪些鱼吃掉了哪些鱼。JOI 君想知道可能成为最后存活者的鱼的条数。在实验中,鱼的编号不会改变,也不能有两条鱼同时吃掉同一条鱼。
请写一个程序,对于给定的 JOI 君的鱼和实验的信息,计算每个第二类行动的答案来让 JOI 君能够证明或证伪自己的观点。注意这只是思想实验,并没有任何鱼真的被吃掉。
输入格式
第一行,一个正整数 N,表示鱼的条数。
第二行,N 个正整数 A1,A2,…,AN,表示每条鱼的大小。
第三行,一个正整数 Q,表示养鱼的天数。
接下来 Q 行,其中第 j (1≤j≤Q) 行包含若干个由空格分隔的整数,其中第一个整数为 Tj,表示操作类型。
- 若 Tj=1,则该行还包含两个正整数 Xj,Yj,表示 JOI 君第 j 天进行了第一类行动。鱼 Xj 的大小变为 Yj。
- 若 Tj=2,则该行还包含两个正整数 Lj,Rj,表示 JOI 君第 j 天进行了第二类行动。JOI 君对编号在 [Lj,Rj] 内的鱼进行了一次实验。
输出格式
对于每次第二类行动(即,对于每个满足 Tj=2 的 j (1≤j≤Q)),输出一行一个整数,表示可能成为最后存活者的鱼的条数。
提示
【样例解释 #1】
在 6 天中,JOI 君进行了以下行动:
- 第一天,他对鱼 1,2,3,4,5 进行了一次实验。
- 第二天,他对鱼 1,2,3 进行了一次实验。
- 第三天,他给鱼 3 吃了秘制食物,使其大小变为 1。
- 第四天,他对鱼 2,3,4,5 进行了一次实验。
- 第五天,他对鱼 1,2,3,4,5 进行了一次实验。
- 第六天,他对鱼 2,3,4 进行了一次实验。
第一天的实验的结果如下:
- 鱼缸中的鱼的大小依次为 [6,4,2,2,6]。
- 例如,经过如下过程,鱼 2 会成为最后存活者。(其中粗体为鱼 2 的大小。)
[6,4,2,2,6](初始状态)⟶ [6,4,4,6](鱼 4 吃掉鱼 3)⟶ [6,8,6](鱼 2 吃掉鱼 4)⟶ [14,6](鱼 2 吃掉鱼 1)⟶ [20](鱼 2 吃掉鱼 5)。
- 类似地,鱼 1,2,3,4,5 都可能成为最后存活者。因此答案为 5。
该样例满足子任务 1,3,6 的限制。
【样例解释 #2】
该样例满足所有子任务的限制。
【样例解释 #3】
该样例满足子任务 1,3,4,6 的限制。
【样例解释 #4】
该样例满足子任务 1,3,5,6 的限制。
【数据范围】
对于所有数据,满足:
- 1≤N,Q≤100000。
- 1≤Ai≤109 (1≤i≤N)。
- Tj∈{1,2}。
- 1≤Xj≤N (1≤j≤Q)。
- 1≤Yj≤109。
- 1≤Lj≤Rj≤N (1≤j≤Q)。
详细子任务附加限制及分值如下表所示:
子任务编号 |
附加限制 |
分值 |
1 |
N≤500,Q≤500 |
5 |
2 |
Q=1,Tj=2,Lj=1,Rj=N (1≤j≤Q) |
8 |
3 |
Q≤1000 |
12 |
4 |
Tj=2 (1≤j≤Q) |
23 |
5 |
对于每个满足 Tj=2 的 j (1≤j≤Q),满足 Lj=1,Rj=N |
35 |
6 |
无附加限制 |
17 |