Problem #3412 - ECNU Online Judge

单点时限: 2.0 sec

内存限制: 256 MB

You are given a sequence $a_{1}, a_{2}, \dots, a_{n}$ . The task is to perform the following queries on it:

Type 1. Given two integers $l$ and $r$ . Reorder the elements of the sequence in such a way (changed part of the sequence is in brackets):
$a_{1}, a_{2}, \dots, a_{n} \Rightarrow a_{1}, a_{2}, \dots, a_{l - 2}, a_{l - 1}, [a_{l + 1}, a_{l}, a_{l + 3}, a_{l + 2}, \dots, a_{r}, a_{r - 1}], a_{r + 1}, a_{r + 2}, \dots, a_{n}$
That is swap the first two elements of segment $[l, r]$ , the second two elements, and so on.
Type 2. Given two integers $l$ and $r$ , print the value of sum $\sum_{i = l}^{r} a_{i}$ .

输入格式

The first line contains two integers $n$ and $q$ . The second line contains $n$ integers $a_{1}, a_{2}, \dots, a_{n}$ , denoting initial sequence.

Each of the next $q$ lines contains three integers $t p_{i}, l_{i}, r_{i}$ , where $t p_{i}$ denotes the type of the query, and $l_{i}$ are $r_{i}$ parameters of the query. It’s guaranteed that for a first-type query $r - l + 1$ will be even.

$2 \leq n \leq 2 \times 10^{5}$
$1 \leq q \leq 2 \times 10^{5}$
$1 \leq a_{i} \leq 10^{6}$
$1 \leq t p_{i} \leq 2$
$1 \leq l_{i} \leq r_{i} \leq n$

输出格式

For each query of the second type print the required sum.

样例

Input

6 4
1 2 3 4 5 6
1 2 5
2 2 3
2 3 4
2 4 5

Output

5
7
9

1 人解决，5 人已尝试。

1 份提交通过，共有 7 份提交。

9.9 EMB 奖励。

创建: 7 年，5 月前.

修改: 7 年，5 月前.

最后提交: 1 年，8 月前.

来源: HackerRank

data structure

3412. Swaps and Sum

输入格式

输出格式

样例

服务

开源

关于我们