配点 : 700 点
問題文
桌子上有黑白棋棋子。 有 N 件。目前从左起 i 部分是 i 为奇数时,黑面朝上,为偶数时,白面朝上。另外,从左边开始 i 块的黑色一侧有一个数字。 B_i 是白色一侧的数字。 写入 W_i 。
我有一个问题 您将得到 Q ,因此请回答所有问题。 i 问题是:
- 从左起
从第 L_i 起
件数最多为 R_i 将所有以外从桌子上移走。然后执行以下操作
重复大于或等于 0 的任意次数。此时,桌子上的棋子所面向的一面所写的数字之和最大是多少?
- 当前放置在桌子上的件数。 r 。 1 \leq i \leq j \leq r 从左边开始 i 一块,从左边开始 一个整数,使得第 j 块所面向的一侧的颜色相同 选择 i 和 按字典顺序比较 j 。从左边开始 对于 i 起 件数最多为 j 之前的所有棋子,棋子所面向的一侧的颜色是从左侧开始的。 如果它与 i 部分不同,则将该部分翻转过来。
所有问题都是独立的, i 即使你在第一个问题中移除一块或翻转一块, i+1 之后的问题不受影响。 输出第
制約
- 1 \leq N \leq 10^5
- 1 \leq B_i \leq 10^9
- 1 \leq W_i \leq 10^9
- 1 \leq Q \leq 10^5
- 1 \leq L_i \leq R_i \leq N
- 所有输入均为整数
入力
输入是按以下格式从标准输入给出的。
N B_1 W_1 \vdots B_N W_N Q L_1 R_1 \vdots L_Q R_Q
出力
Q 行。i 在线 i 个问题的答案。 对于第
入力例 1
4 1 2 3 4 5 6 7 8 3 2 4 1 3 1 2
出力例 1
18 10 5
1 个问题, i = 1, j = 3 作为 1 最好只操作一次。写在桌子上剩下的棋子面向的一侧的数字是 4, 6, 8 。 对于
2 问题,最好什么都不做。 对于
3 问题,您首先无法执行任何操作。
入力例 2
4 17 59 59 91 78 71 24 19 3 1 3 2 4 2 3
出力例 2
186 188 169
原案: 森林