CF1443E.Long Permutation

一个排列是一个长度为 $n$ 的整数序列，包含从 $1$ 到 $n$ 的每个数字且每个数字恰好出现一次。例如，$[1]$、$[4, 3, 5, 1, 2]$、$[3, 2, 1]$ 都是排列，而 $[1, 1]$、$[4, 3, 1]$、$[2, 3, 4]$ 不是排列。

如果两个长度相同的排列 $a$ 和 $b$，在第一个不同的位置 $i$ 满足 $a[i] < b[i]$，则称排列 $a$ 字典序小于排列 $b$。例如，排列 $[1, 3, 2, 4]$ 字典序小于排列 $[1, 3, 4, 2]$，因为前两个元素相等，第三个元素第一个排列更小。

对于长度为 $n$ 的排列 $a$，它的下一个排列是长度为 $n$ 的、字典序大于 $a$ 的最小排列。例如：

• 对于排列 $[2, 1, 4, 3]$，下一个排列是 $[2, 3, 1, 4]$；
• 对于排列 $[1, 2, 3]$，下一个排列是 $[1, 3, 2]$；
• 对于排列 $[2, 1]$，不存在下一个排列。

给定一个整数 $n$，初始排列为 $a = [1, 2, \ldots, n]$，即 $a[i] = i$（$1 \le i \le n$）。

你需要处理 $q$ 个操作，操作有两种类型：

• $1\ l\ r$：查询区间 $[l, r]$ 上所有元素的和。更正式地说，需要计算 $a[l] + a[l+1] + \ldots + a[r]$。
• $2\ x$：将当前排列替换为它的下一个排列，重复 $x$ 次。例如，如果 $x=2$ 且当前排列为 $[1, 3, 4, 2]$，则执行如下变化链 $[1, 3, 4, 2] \rightarrow [1, 4, 2, 3] \rightarrow [1, 4, 3, 2]$。

对于每个 $1$ 型操作，输出所需的区间和。

第一行包含两个整数 $n$（$2 \le n \le 2 \times 10^5$）和 $q$（$1 \le q \le 2 \times 10^5$），分别表示初始排列的长度和操作数。

接下来的 $q$ 行，每行表示一个操作。$1$ 型操作包含三个整数 $1\ l\ r$（$1 \le l \le r \le n$），$2$ 型操作包含两个整数 $2\ x$（$1 \le x \le 10^5$）。

保证所有 $2$ 型操作都可以被执行。

对于每个 $1$ 型操作，输出一行一个整数，表示所求的区间和。

初始排列为 $[1, 2, 3, 4]$。操作过程如下：

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$。

由 ChatGPT 4.1 翻译