3412. Swaps and Sum

单点时限: 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 $tp_i, l_i, r_i$, where $tp_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 tp_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 人解决,2 人已尝试。

1 份提交通过,共有 2 份提交。

9.6 EMB 奖励。

创建: 2 年,11 月前.

修改: 2 年,11 月前.

最后提交: 2 年,11 月前.

来源: HackerRank

题目标签