Long Permutation (Codeforces 1443E)
Tags: Math, two pointers

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.

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.

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

Sample Inputs:
4 4
1 2 4
2 3
1 1 2
1 3 4

Sample Outputs:
9
4
6

Solution (Python):
import io, os
from math import *
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
manual = 20
(n, Q) = map(int, input().split())
after = min(manual, n)
before = n - after
ind = 0

def unrankperm(i):
    unused = [i + 1 for i in range(after)]
    r = []
    for j in range(after)[::-1]:
        use = i // factorial(j)
        r.append(unused[use])
        del unused[use]
        i -= use * factorial(j)
    return r
p = unrankperm(ind)
for _ in range(Q):
    q = list(map(int, input().split()))
    if q[0] == 1:
        (l, r) = q[1:]
        amt = 0
        if l <= before:
            amt += r * (r + 1) // 2 if r <= before else before * (before + 1) // 2
            amt -= l * (l - 1) // 2
            l = before + 1
        if r > before:
            amt += sum(p[l - 1 - before:r - before]) + (r - l + 1) * before
        print(amt)
    else:
        ind += q[1]
        p = unrankperm(ind)

Solution (Python):
import io, os
from math import *
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
manual = 20
(n, Q) = map(int, input().split())
after = min(manual, n)
before = n - after
ind = 0

def unrankperm(i):
    unused = [i + 1 for i in range(after)]
    r = []
    for j in range(after)[::-1]:
        use = i // factorial(j)
        r.append(unused[use])
        del unused[use]
        i -= use * factorial(j)
    return r
p = unrankperm(ind)
for _ in range(Q):
    q = list(map(int, input().split()))
    if q[0] == 1:
        (l, r) = q[1:]
        amt = 0
        if l <= before:
            amt += r * (r + 1) // 2 if r <= before else before * (before + 1) // 2
            amt -= l * (l - 1) // 2
            l = before + 1
        if r > before:
            amt += sum(p[l - 1 - before:r - before]) + (r - l + 1) * before
        print(amt)
    else:
        ind += q[1]
        p = unrankperm(ind)

Solution (Python):
import io, os
from math import *
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
manual = 20
(n, Q) = map(int, input().split())
after = min(manual, n)
before = n - after
ind = 0

def unrankperm(i):
    unused = [i + 1 for i in range(after)]
    r = []
    for j in range(after)[::-1]:
        use = i // factorial(j)
        r.append(unused[use])
        del unused[use]
        i -= use * factorial(j)
    return r
p = unrankperm(ind)
for _ in range(Q):
    q = list(map(int, input().split()))
    if q[0] == 1:
        (l, r) = q[1:]
        amt = 0
        if l <= before:
            amt += r * (r + 1) // 2 if r <= before else before * (before + 1) // 2
            amt -= l * (l - 1) // 2
            l = before + 1
        if r > before:
            amt += sum(p[l - 1 - before:r - before]) + (r - l + 1) * before
        print(amt)
    else:
        ind += q[1]
        p = unrankperm(ind)