← 返回题目列表

AtCoder · tkppc6_2_h

H. 黑白棋棋子

中文机器翻译题面 查看原题

配点 : 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

原案: 森林