Frets On Fire (Codeforces 1119D)
Tags: Others, binary search

Miyako came to the flea kingdom with a ukulele. She became good friends with local flea residents and played beautiful music for them every day.In return, the fleas made a bigger ukulele for her: it has $$$n$$$ strings, and each string has $$$(10^{18} + 1)$$$ frets numerated from $$$0$$$ to $$$10^{18}$$$. The fleas use the array $$$s_1, s_2, \ldots, s_n$$$ to describe the ukulele's tuning, that is, the pitch of the $$$j$$$-th fret on the $$$i$$$-th string is the integer $$$s_i + j$$$.Miyako is about to leave the kingdom, but the fleas hope that Miyako will answer some last questions for them.Each question is in the form of: "How many different pitches are there, if we consider frets between $$$l$$$ and $$$r$$$ (inclusive) on all strings?"Miyako is about to visit the cricket kingdom and has no time to answer all the questions. Please help her with this task!Formally, you are given a matrix with $$$n$$$ rows and $$$(10^{18}+1)$$$ columns, where the cell in the $$$i$$$-th row and $$$j$$$-th column ($$$0 \le j \le 10^{18}$$$) contains the integer $$$s_i + j$$$. You are to answer $$$q$$$ queries, in the $$$k$$$-th query you have to answer the number of distinct integers in the matrix from the $$$l_k$$$-th to the $$$r_k$$$-th columns, inclusive.

Input: The first line contains an integer $$$n$$$ ($$$1 \leq n \leq 100\,000$$$) — the number of strings.The second line contains $$$n$$$ integers $$$s_1, s_2, \ldots, s_n$$$ ($$$0 \leq s_i \leq 10^{18}$$$) — the tuning of the ukulele.The third line contains an integer $$$q$$$ ($$$1 \leq q \leq 100\,000$$$) — the number of questions.The $$$k$$$-th among the following $$$q$$$ lines contains two integers $$$l_k$$$，$$$r_k$$$ ($$$0 \leq l_k \leq r_k \leq 10^{18}$$$) — a question from the fleas.

Output: Output one number for each question, separated by spaces — the number of different pitches.

Note: For the first example, the pitches on the $$$6$$$ strings are as follows.$$$$$$ \begin{matrix} \textbf{Fret} & \textbf{0} & \textbf{1} & \textbf{2} & \textbf{3} & \textbf{4} & \textbf{5} & \textbf{6} & \textbf{7} & \ldots \\ s_1: & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & \dots \\ s_2: & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & \dots \\ s_3: & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & \dots \\ s_4: & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & \dots \\ s_5: & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & \dots \\ s_6: & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & \dots \end{matrix} $$$$$$There are $$$5$$$ different pitches on fret $$$7$$$ — $$$8, 10, 11, 12, 16$$$.There are $$$10$$$ different pitches on frets $$$0, 1, 2$$$ — $$$1, 2, 3, 4, 5, 6, 7, 9, 10, 11$$$.

Sample Inputs:
6
3 1 4 1 5 9
3
7 7
0 2
8 17

2
1 500000000000000000
2
1000000000000000000 1000000000000000000
0 1000000000000000000

Sample Outputs:
5 10 18

2 1500000000000000000

Solution (Python):
import os
import sys
from io import IOBase
from bisect import bisect_right, bisect_left
if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from cStringIO import StringIO
    from future_builtins import ascii, filter, hex, map, oct, zip
else:
    from io import BytesIO as StringIO
(sys.stdout, stream) = (IOBase(), StringIO())
sys.stdout.flush = lambda : os.write(1, stream.getvalue()) and (not stream.truncate(0)) and stream.seek(0)
sys.stdout.write = stream.write if sys.version_info[0] < 3 else lambda s: stream.write(s.encode())
(input, flush) = (sys.stdin.readline, sys.stdout.flush)
input = StringIO(os.read(0, os.fstat(0).st_size)).readline

def main():
    n = int(input())
    s = list(map(int, input().split()))
    if n == 1:
        q = int(input())
        out = [0] * q
        for u in range(q):
            (a, b) = map(int, input().split())
            out[u] = str(b - a + 1)
        print(' '.join(out))
        exit()
    s.sort()
    diffs = [s[i + 1] - s[i] for i in range(n - 1)]
    diffs.sort()
    parts = [0] * (n - 1)
    parts[0] = diffs[0] * n
    for i in range(n - 2):
        parts[i + 1] = parts[i] + (diffs[i + 1] - diffs[i]) * (n - i - 1)
    q = int(input())
    out = [0] * q
    for u in range(q):
        (a, b) = map(int, input().split())
        size = b - a + 1
        if size <= diffs[0]:
            out[u] = n * size
        elif size >= diffs[-1]:
            out[u] = parts[-1] + size - diffs[-1]
        else:
            big = n - 2
            sml = 0
            curr = (n - 2) // 2
            while big - sml > 1:
                if size > diffs[curr]:
                    sml = curr
                    curr = (big + sml) // 2
                elif size < diffs[curr]:
                    big = curr
                    curr = (big + sml) // 2
                else:
                    big = sml = curr
            if big == sml:
                out[u] = parts[big]
            else:
                rat = (parts[big] - parts[sml]) // (diffs[big] - diffs[sml])
                out[u] = parts[sml] + rat * (size - diffs[sml])
    out = [str(guy) for guy in out]
    print(' '.join(out))
main()

Solution (Python):
from __future__ import division, print_function
import os
import sys
from io import IOBase
from bisect import bisect_right, bisect_left
if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from cStringIO import StringIO
    from future_builtins import ascii, filter, hex, map, oct, zip
else:
    from io import BytesIO as StringIO
(sys.stdout, stream) = (IOBase(), StringIO())
sys.stdout.flush = lambda : os.write(1, stream.getvalue()) and (not stream.truncate(0)) and stream.seek(0)
sys.stdout.write = stream.write if sys.version_info[0] < 3 else lambda s: stream.write(s.encode())
(input, flush) = (sys.stdin.readline, sys.stdout.flush)
input = StringIO(os.read(0, os.fstat(0).st_size)).readline

def main():
    n = int(input())
    s = sorted((int(si) for si in input().split()))
    diffs = [0] * (n - 1)
    for i in range(n - 1):
        diffs[i] = s[i + 1] - s[i]
    diffs.sort()
    cumsum = [0] * n
    for i in range(n - 1):
        cumsum[i + 1] = cumsum[i] + diffs[i]
    q = int(input())
    for _ in range(q):
        (l, r) = map(int, input().split())
        res = (r - l + 1) * n
        ind = bisect_left(diffs, r - l + 1)
        res -= ind * (r - l + 1) - cumsum[ind]
        print(res, end=' ')
if __name__ == '__main__':
    main()

Solution (Python):
def main():
    from bisect import bisect
    from itertools import accumulate, chain
    from sys import stdin, stdout
    input = stdin.readline
    input()
    s = sorted(set(map(int, input().split())))
    n = len(s)
    inp = sorted((a - b for (a, b) in zip(s[1:], s)))
    acc = tuple(chain(accumulate(inp), (0,)))
    for _ in range(int(input())):
        (l_, r) = map(int, input().split())
        d = r + 1 - l_
        i = bisect(inp, d)
        stdout.write(f'{acc[i - 1] + (n - i) * d} ')
main()