CF717F.Heroes of Making Magic III

I’m strolling on sunshine, yeah-ah! And doesn’t it feel good! Well, it certainly feels good for our Heroes of Making Magic, who are casually walking on a one-directional road, fighting imps. Imps are weak and feeble creatures and they are not good at much. However, Heroes enjoy fighting them. For fun, if nothing else.

Our Hero, Ignatius, simply adores imps. He is observing a line of imps, represented as a zero-indexed array of integers a of length n, where a__i denotes the number of imps at the i-th position. Sometimes, imps can appear out of nowhere. When heroes fight imps, they select a segment of the line, start at one end of the segment, and finish on the other end, without ever exiting the segment. They can move exactly one cell left or right from their current position and when they do so, they defeat one imp on the cell that they moved to, so, the number of imps on that cell decreases by one. This also applies when heroes appear at one end of the segment, at the beginning of their walk.

Their goal is to defeat all imps on the segment, without ever moving to an empty cell in it (without imps), since they would get bored. Since Ignatius loves imps, he doesn’t really want to fight them, so no imps are harmed during the events of this task. However, he would like you to tell him whether it would be possible for him to clear a certain segment of imps in the above mentioned way if he wanted to.

You are given q queries, which have two types:

• 1 a b k — denotes that k imps appear at each cell from the interval [a, b]
• 2 a b - asks whether Ignatius could defeat all imps on the interval [a, b] in the way described above

我在阳光下漫步，耶—啊！这感觉难道不好吗？当然，这对我们的“魔法制造英雄”来说感觉确实很好，他们正悠闲地走在一条单向道路上，与小恶魔作战。小恶魔是弱小而孱弱的生物，几乎一无是处。然而，英雄们却乐于与它们战斗——纯粹为了娱乐，别无其他。

我们的英雄伊格纳提乌斯（Ignatius）简直痴迷于小恶魔。他正观察着一排小恶魔，该排列用一个长度为 $ n $ 的、以零为起始索引的整数数组 $ a $ 表示，其中 $ a_i $ 表示第 $ i $ 个位置上的小恶魔数量。有时，小恶魔会凭空出现。当英雄与小恶魔战斗时，他们会选定该排列中的一段区间，从该区间的某一端出发，走到另一端，且全程不得离开该区间。他们每次只能向左或向右移动一格；每当他们如此移动时，便会消灭所移至格子上的一个小恶魔，即该格子上的小恶魔数量减 $ 1 $。当英雄在区间一端初始出现时，此规则同样适用。

他们的目标是在不踏足该区间内任何空格子（即小恶魔数量为 $ 0 $ 的格子）的前提下，消灭该区间内的所有小恶魔——否则他们会感到无聊。由于伊格纳提乌斯热爱小恶魔，他其实并不想真正与它们战斗，因此本题中不会有任何小恶魔受到伤害。但他希望你能告诉他：若他愿意，是否有可能以上述方式清空某个指定区间内的所有小恶魔？

你将收到 $ q $ 个查询，分为两类：

• 1 a b k — 表示在区间 $[a,\,b]$ 内的每个位置上都新增 $ k $ 个小恶魔；
• 2 a b — 询问伊格纳提乌斯是否能以上述方式消灭区间 $[a,\,b]$ 内的所有小恶魔。

The first line contains a single integer n (1 ≤ n ≤ 200 000), the length of the array a. The following line contains n integers _a_1, _a_2, ..., a__n (0 ≤ a__i ≤ 5 000), the initial number of imps in each cell. The third line contains a single integer q (1 ≤ q ≤ 300 000), the number of queries. The remaining q lines contain one query each. Each query is provided by integers a, b and, possibly, k (0 ≤ a ≤ b < n, 0 ≤ k ≤ 5 000).

第一行包含一个整数 $n$（$1 \leq n \leq 200\,000$），表示数组 $a$ 的长度。
接下来一行包含 $n$ 个整数 $a_1,\,a_2,\,\dots,\,a_n$（$0 \leq a_i \leq 5\,000$），表示每个格子中初始的恶魔数量。
第三行包含一个整数 $q$（$1 \leq q \leq 300\,000$），表示查询的数量。
接下来的 $q$ 行每行包含一个查询。每个查询由整数 $a$、$b$ 和（可能存在的）$k$ 给出（$0 \leq a \leq b < n$，$0 \leq k \leq 5\,000$）。

For each second type of query output 1 if it is possible to clear the segment, and 0 if it is not.

对于每种第二类查询，如果可以清空该区间，则输出 1；否则输出 0。

For the first query, one can easily check that it is indeed impossible to get from the first to the last cell while clearing everything. After we add 1 to the second position, we can clear the segment, for example by moving in the following way: .

对于第一个查询，可以很容易地验证：确实无法在清空所有格子的同时从第一个格子到达最后一个格子。在第二个位置加 1 后，我们便可以清空该区间，例如按如下方式移动：