【PAT】全排列（待补充）

题目描述

明明同学在学习了递归搜索算法之后，发现可以用这个算法求出长度为 n 的所有排列。排列是长度为 n 的 1 到 n 的整数序列，每个整数恰好包含一次。例如，[1]，[4,3,5,1,2]，[3,2,1] 是排列，而 [1,1]，[4,3,1]，[2,3,4] 不是排列。

这对于明明同学来说太简单了，他想研究所有排列的规律。显然，长度为 n 的排列一共有 n! 个排列。为了便于研究，明明同学把这些排列按照字典序排序。如果有两个排列 a ，b ，有 a[i]=bi,a[j]<b[j] ，就称排列 a 的字典序小于 b 。长度为 n 的排列 a 的下一个排列是在字典上小于的长度为 n 的字典上最小的排列b。

现在明明同学遇到了困难，请你帮帮他。

输入格式：

一行一个整数 n(2≤n≤2⋅10^​5) 和一个整数 q(1≤q≤2⋅10 ^​5)，分别表示序列的长度和询问的次数。序列的初始排列为 1,2,…n，即 a[i]=i(1≤i≤n) 。

接下来 q 行两种格式的询问，输入格式如下：

1,l,r ，查询区间 [l,r] 上所有元素的总和，即你需要求出 a[l]+a[l+1]+…+a[r] 。
2,x ，表示将当前排列替换为下 x 个排列。例如，如果 x=2 并且当前排列为 [1,3,4,2] ，那么我们应该将排列替换为 [1,3,4,2]⟶[1,4,2,3]⟶[1,4,3,2] 。保证这个询问可以处理。即 ∑x<n! 。

输出描述：

对于每一个第一种类型的询问，输出一行一个整数表示答案。

样例输入：

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

样例输出：

9
4
6

样例解释：

初始排列为 [1,2,3,4] ，区间 [2,4] 的和为 2+3+4=9 ；

将当前排列替换为下 3 个排列，即 [1,2,3,4]⟶[1,2,4,3]⟶[1,3,2,4]⟶[1,3,4,2] ；

区间 [1,2] 的和为 1+3=4；

区间 [3,4] 的和为 4+2=6 。

代码

#include <bits/stdc++.h>
using namespace std;
int a[200001];
int n,q;
int main()
{
    cin>>n>>q;
    for(int i=1;i<=n;i++)
        a[i]=i;
    while(q--)
    {
        int note;
        cin>>note;
        if(note==1)
        {
            int l,r,i,sum=0;
            cin>>l>>r;
            for(i=l;i<=r;i++)
                sum+=a[i];
            cout<<sum<<endl;
        }
        else
        {
            int x;
            cin>>x;
            while(x--)
            {
                next_permutation(a,a+n+1);
            }
        }
    }
    return 0;
}

（超时了，优化方法待补充）