分数: 466 分
问题陈述
高桥正计划租用商业街的连续路段来设立活动场地。
商店街有 N 部分从左到右排成一排。
租金 i左起第节 (1 \leq i \leq N) is A_i 日元。
另外,对于 i左起第节, C_i = 1 如果有停车位,并且 C_i = 0 如果没有。
高桥正在考虑租房 K 连续部分。
也就是说,他选择一个整数 l (1 \leq l \leq N-K+1) 并租用 K 部分 l-第 (l+K-1)从左起第一个。
Q 操作将按顺序执行。的 j第次操作 (1 \leq j \leq Q) 由整数确定 T_j 并且是以下之一:
- T_j = 1 (租金变化):整数 给出了 X_j, Y_j 。改变租金 X_j从左到右的第节 Y_j 日元。此更改会影响所有后续操作。
- T_j = 2 (查询):整数
给出了 X_j 。在所有方法中准确选择 K 连续的部分,考虑那些选择的 K 部分至少包含 X_j 有停车位的路段(有停车位的路段) C_i = 1)。如果存在这样的选择,则输出所选选项的最小可能总租金 K 部分。如果不存在这样的选择,则输出
IMPOSSIBLE.
请注意这些值 C_i 代表停车位的存在或不存在,不会通过操作而改变。
对于每个操作 T_j = 2,输出答案。
约束
- 1 \leq K \leq N \leq 10^5
- 1 \leq Q \leq 5 \times 10^4
- 1 \leq A_i \leq 10^9
- C_i \in \{0, 1\}
- T_j \in \{1, 2\}
- 当 T_j = 1: 1 \leq X_j \leq N, 1 \leq Y_j \leq 10^9
- 当 T_j = 2: 0 \leq X_j \leq K, Y_j = 0
- 至少有一项操作 T_j = 2
- 所有输入均为整数
输入
N K Q A_1 A_2 \cdots A_N C_1 C_2 \cdots C_N T_1 X_1 Y_1 T_2 X_2 Y_2 \vdots T_Q X_Q Y_Q
每个操作都以整数三元组的形式给出 (T_j, X_j, Y_j)。当 给出了 T_j = 2, Y_j = 0 ,但这只是为了统一输入格式,并没有在解决方案中使用。
输出
对于每个操作 T_j = 2,如果有效选择,则在单行上输出最低总租金 K 存在满足条件的连续部分,或者 IMPOSSIBLE 如果不存在这样的选择。
示例输入 1
5 3 5 10 20 5 7 8 1 0 1 0 1 2 1 0 2 2 0 1 2 1 2 1 0 2 2 0
示例输出 1
20 20 13 16
示例输入 2
4 2 3 5 6 7 8 0 0 0 0 2 1 0 1 3 1 2 1 0
示例输出 2
IMPOSSIBLE IMPOSSIBLE
示例输入 3
12 4 10 15 3 22 8 7 13 5 19 11 2 17 6 1 0 1 1 0 0 1 0 1 1 0 1 2 2 0 2 3 0 1 5 4 2 2 0 1 10 20 2 1 0 1 1 30 2 4 0 1 8 1 2 3 0
示例输出 3
33 36 30 30 IMPOSSIBLE 37
示例输入 4
25 7 20 31 12 45 7 23 18 60 5 14 39 27 8 50 16 22 41 9 33 11 28 6 19 35 24 10 1 0 0 1 1 0 1 0 1 0 0 1 1 0 1 0 1 1 0 0 1 0 1 0 1 2 3 0 2 5 0 1 7 4 2 4 0 1 14 3 2 2 0 1 1 100 2 5 0 1 20 2 2 1 0 1 25 70 2 6 0 1 12 1 2 4 0 1 18 55 2 3 0 1 9 40 2 0 0 1 4 9 2 5 0
示例输出 4
133 179 110 110 166 107 IMPOSSIBLE 110 108 114 181
示例输入 5
1 1 5 1000000000 0 2 0 0 2 1 0 1 1 1 2 0 0 2 1 0
示例输出 5
1000000000 IMPOSSIBLE 1 IMPOSSIBLE