AT_tkppc6_2_h.Reversi Pieces

桌子上有 $N$ 个黑白棋子。现在，从左起第 $i$ 个棋子，如果 $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$ 个不同，则将该棋子翻面。

注意，所有询问互相独立，在第 $i$ 个询问中移除或翻转棋子不会影响第 $i+1$ 个及之后的询问。

输入按以下格式从标准输入给出。

$N$
$B_1$ $W_1$
$B_2$ $W_2$
$\vdots$
$B_N$ $W_N$
$Q$
$L_1$ $R_1$
$L_2$ $R_2$
$\vdots$
$L_Q$ $R_Q$

输出 $Q$ 行，第 $i$ 行输出第 $i$ 个询问的答案。

数据范围

• $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$
• 所有输入均为整数

样例解释 1

对于第 $1$ 个询问，选择 $i=1, j=3$，只操作一次是最优的。桌上剩下的棋子朝上的数字依次为 $4, 6, 8$。对于第 $2$ 个询问，一次操作都不进行是最优的。对于第 $3$ 个询问，无法进行任何操作。

样例解释 2

原案: Forested

由 ChatGPT 4.1 翻译