codeforces#P1443E. Long Permutation
Long Permutation
Description
A permutation is a sequence of integers from $1$ to $n$ of length $n$ containing each number exactly once. For example, $[1]$, $[4, 3, 5, 1, 2]$, $[3, 2, 1]$ — are permutations, and $[1, 1]$, $[4, 3, 1]$, $[2, 3, 4]$ — no.
Permutation $a$ is lexicographically smaller than permutation $b$ (they have the same length $n$), if in the first index $i$ in which they differ, $a[i] < b[i]$. For example, the permutation $[1, 3, 2, 4]$ is lexicographically smaller than the permutation $[1, 3, 4, 2]$, because the first two elements are equal, and the third element in the first permutation is smaller than in the second.
The next permutation for a permutation $a$ of length $n$ — is the lexicographically smallest permutation $b$ of length $n$ that lexicographically larger than $a$. For example:
- for permutation $[2, 1, 4, 3]$ the next permutation is $[2, 3, 1, 4]$;
- for permutation $[1, 2, 3]$ the next permutation is $[1, 3, 2]$;
- for permutation $[2, 1]$ next permutation does not exist.
You are given the number $n$ — the length of the initial permutation. The initial permutation has the form $a = [1, 2, \ldots, n]$. In other words, $a[i] = i$ ($1 \le i \le n$).
You need to process $q$ queries of two types:
- $1$ $l$ $r$: query for the sum of all elements on the segment $[l, r]$. More formally, you need to find $a[l] + a[l + 1] + \ldots + a[r]$.
- $2$ $x$: $x$ times replace the current permutation with the next permutation. For example, if $x=2$ and the current permutation has the form $[1, 3, 4, 2]$, then we should perform such a chain of replacements $[1, 3, 4, 2] \rightarrow [1, 4, 2, 3] \rightarrow [1, 4, 3, 2]$.
For each query of the $1$-st type output the required sum.
The first line contains two integers $n$ ($2 \le n \le 2 \cdot 10^5$) and $q$ ($1 \le q \le 2 \cdot 10^5$), where $n$ — the length of the initial permutation, and $q$ — the number of queries.
The next $q$ lines contain a single query of the $1$-st or $2$-nd type. The $1$-st type query consists of three integers $1$, $l$ and $r$ $(1 \le l \le r \le n)$, the $2$-nd type query consists of two integers $2$ and $x$ $(1 \le x \le 10^5)$.
It is guaranteed that all requests of the $2$-nd type are possible to process.
For each query of the $1$-st type, output on a separate line one integer — the required sum.
Input
The first line contains two integers $n$ ($2 \le n \le 2 \cdot 10^5$) and $q$ ($1 \le q \le 2 \cdot 10^5$), where $n$ — the length of the initial permutation, and $q$ — the number of queries.
The next $q$ lines contain a single query of the $1$-st or $2$-nd type. The $1$-st type query consists of three integers $1$, $l$ and $r$ $(1 \le l \le r \le n)$, the $2$-nd type query consists of two integers $2$ and $x$ $(1 \le x \le 10^5)$.
It is guaranteed that all requests of the $2$-nd type are possible to process.
Output
For each query of the $1$-st type, output on a separate line one integer — the required sum.
Samples
4 4
1 2 4
2 3
1 1 2
1 3 4
9
4
6
Note
Initially, the permutation has the form $[1, 2, 3, 4]$. Queries processing is as follows:
- $2 + 3 + 4 = 9$;
- $[1, 2, 3, 4] \rightarrow [1, 2, 4, 3] \rightarrow [1, 3, 2, 4] \rightarrow [1, 3, 4, 2]$;
- $1 + 3 = 4$;
- $4 + 2 = 6$