Long Permutation

题意翻译

你需要维护一个长度为$n$的排列$P$和$2$种操作： - $1 \ l \ r$ 求出$\sum_{i=l}^r P_i$ - $2 \ x$ 将$P$替换为$P$的下$x$个排列 排列$P$初始为$[1,2,3,\cdots n]$ 总共有$q$次操作 关于操作$2$的解释 比如排列$P$为$[1,2,3,4]$ 对它进行操作$2 \ 3$ $[1,2,3,4]\to[1,2,4,3]\to[1,3,2,4]\to[1,3,4,2]$ 因此$P$变为$[1,3,4,2]$ 数据范围： $n,q\leq2\times 10^5,x\leq 10^5$

题目描述

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.

输入输出样例

输入样例 #1

4 4
1 2 4
2 3
1 1 2
1 3 4

输出样例 #1

9
4
6

说明

Initially, the permutation has the form $ [1, 2, 3, 4] $ . Queries processing is as follows: 1. $ 2 + 3 + 4 = 9 $ ; 2. $ [1, 2, 3, 4] \rightarrow [1, 2, 4, 3] \rightarrow [1, 3, 2, 4] \rightarrow [1, 3, 4, 2] $ ; 3. $ 1 + 3 = 4 $ ; 4. $ 4 + 2 = 6 $