Swap and Range Sum

AtCoder

IDabc442_d

Time2000ms

Memory256MB

Difficulty—

You are given a sequence $A=(A_1,A_2,\dots,A_N)$ of length $N$. Process $Q$ queries in order. Each query is in one of the following formats: * `1 x` : Swap the values of $A_x$ and $A_{x+1}$. * `2 l r` : Find the value of $\displaystyle \sum_{l\leq i\leq r} A_i$. ## Constraints * $2\leq N \leq 2\times 10^5$ * $1\leq Q \leq 5\times 10^5$ * $1\leq A_i \leq 10^4$ * For queries of the first type, $1\leq x \leq N-1$. * For queries of the second type, $1\leq l\leq r \leq N$. * All input values are integers. ## Input The input is given from Standard Input in the following format: $N$ $Q$ $A_1$ $A_2$ $\dots$ $A_N$ $\text{query}_1$ $\text{query}_2$ $\vdots$ $\text{query}_Q$ Here, $\text{query}_i$ represents the $i$\-th query and is given in one of the following formats: $1$ $x$ $2$ $l$ $r$ [samples]

Samples

Input #1

Output #1

3
17

*   In the $1$\-st query, swap the values of $A_2$ and $A_3$. This makes $A=(2,1,7,8)$.
*   In the $2$\-nd query, find the value of $A_1+A_2$. The answer is $2+1=3$.
*   In the $3$\-rd query, swap the values of $A_1$ and $A_2$. This makes $A=(1,2,7,8)$.
*   In the $4$\-th query, find the value of $A_2+A_3+A_4$. The answer is $2+7+8=17$.

Input #2

8 10
22 75 26 45 72 81 47 29
2 2 7
2 6 8
2 4 4
1 2
2 1 3
1 1
2 2 4
1 2
1 4
2 1 1

Output #2

API Response (JSON)

{
  "problem": {
    "name": "Swap and Range Sum",
    "description": {
      "content": "You are given a sequence $A=(A_1,A_2,\\dots,A_N)$ of length $N$. Process $Q$ queries in order. Each query is in one of the following formats: *   `1 x` : Swap the values of $A_x$ and $A_{x+1}$. *   `2",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc442_d"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given a sequence $A=(A_1,A_2,\\dots,A_N)$ of length $N$.\nProcess $Q$ queries in order. Each query is in one of the following formats:\n\n*   `1 x` : Swap the values of $A_x$ and $A_{x+1}$.\n*   `2...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments