Illumination (Codeforces 1728G)
Tags: Math, two pointers

Consider a segment $$$[0, d]$$$ of the coordinate line. There are $$$n$$$ lanterns and $$$m$$$ points of interest in this segment.For each lantern, you can choose its power — an integer between $$$0$$$ and $$$d$$$ (inclusive). A lantern with coordinate $$$x$$$ illuminates the point of interest with coordinate $$$y$$$ if $$$|x - y|$$$ is less than or equal to the power of the lantern.A way to choose the power values for all lanterns is considered valid if every point of interest is illuminated by at least one lantern.You have to process $$$q$$$ queries. Each query is represented by one integer $$$f_i$$$. To answer the $$$i$$$-th query, you have to:  add a lantern on coordinate $$$f_i$$$;  calculate the number of valid ways to assign power values to all lanterns, and print it modulo $$$998244353$$$;  remove the lantern you just added. 

Input: The first line contains three integers $$$d$$$, $$$n$$$ and $$$m$$$ ($$$4 \le d \le 3 \cdot 10^5$$$; $$$1 \le n \le 2 \cdot 10^5$$$; $$$1 \le m \le 16$$$) — the size of the segment, the number of lanterns and the number of points of interest, respectively.The second line contains $$$n$$$ integers $$$l_1, l_2, \dots, l_n$$$ ($$$1 \le l_i \le d - 1$$$), where $$$l_i$$$ is the coordinate of the $$$i$$$-th lantern.The third line contains $$$m$$$ integers $$$p_1, p_2, \dots, p_m$$$ ($$$1 \le p_i \le d - 1$$$), where $$$p_i$$$ is the coordinate of the $$$i$$$-th point of interest.The fourth line contains one integer $$$q$$$ ($$$1 \le q \le 5 \cdot 10^5$$$) — the number of queries.The fifth line contains $$$q$$$ integers $$$f_1, f_2, \dots, f_q$$$ ($$$1 \le f_i \le d - 1$$$), where $$$f_i$$$ is the integer representing the $$$i$$$-th query.Additional constraint on the input: during the processing of each query, no coordinate contains more than one object (i. e. there cannot be two or more lanterns with the same coordinate, two or more points of interest with the same coordinate, or a lantern and a point of interest with the same coordinate).

Output: For each query, print one integer — the answer to it, taken modulo $$$998244353$$$.


Sample Inputs:
6 1 1
4
3
3
2 1 5

6 1 2
4
2 5
2
1 3

20 1 2
11
15 7
1
8

20 3 5
5 7 18
1 6 3 10 19
5
4 17 15 8 9

Sample Outputs:
48
47
47

44
46

413

190431
187503
188085
189903
189708

Solution (Python):
input = __import__('sys').stdin.readline
MOD = 998244353
(d, n, m) = map(int, input().split())
lamps = list(sorted(map(int, input().split())))
points = list(sorted(map(int, input().split())))
positions = [x for x in points]
positions.append(0)
positions.append(d)
for i in range(m):
    for j in range(i + 1, m):
        mid = (points[i] + points[j]) // 2
        positions.append(mid)
        positions.append(mid + 1)
positions = list(sorted(set(positions)))
posmap = {x: i for (i, x) in enumerate(positions)}
i = 0
queryL = []
for p in points:
    queries = [0] * len(positions)
    while positions[i] < p:
        i += 1
    j = i
    q = 1
    for x in lamps:
        if x <= p:
            continue
        while x > positions[j]:
            queries[j] = q
            j += 1
        q = q * (x - p) % MOD
    while j < len(positions):
        queries[j] = q
        j += 1
    queryL.append(queries)
i = len(positions) - 1
queryR = []
for p in points[::-1]:
    queries = [0] * len(positions)
    while positions[i] > p:
        i -= 1
    j = i
    q = 1
    for x in lamps[::-1]:
        if x > p:
            continue
        while x < positions[j]:
            queries[j] = q
            j -= 1
        q = q * (p - x) % MOD
    while j >= 0:
        queries[j] = q
        j -= 1
    queryR.append(queries)
queryR = queryR[::-1]
querySums = [[[0] * len(positions) for _ in range(len(points))] for _ in range(2)]
current_ans = 0
for mask in range(1, 1 << m):
    keys = []
    prev_idx = -1
    popcnt = 0
    q = 1
    for i in range(m):
        if mask >> i & 1:
            p = points[i]
            if prev_idx == -1:
                keys.append((1, i, 0))
                q = q * queryR[i][0] % MOD
            else:
                prev_p = points[prev_idx]
                mid = (prev_p + p) // 2
                keys.append((0, prev_idx, posmap[mid]))
                q = q * queryL[prev_idx][posmap[mid]] % MOD
                keys.append((1, i, posmap[mid + 1]))
                q = q * queryR[i][posmap[mid + 1]] % MOD
            prev_idx = i
            popcnt += 1
    keys.append((0, prev_idx, len(positions) - 1))
    q = q * queryL[prev_idx][-1] % MOD
    if popcnt & 1:
        current_ans = (current_ans - q) % MOD
        for (i, j, k) in keys:
            querySums[i][j][k] = (querySums[i][j][k] - q) % MOD
    else:
        current_ans = (current_ans + q) % MOD
        for (i, j, k) in keys:
            querySums[i][j][k] = (querySums[i][j][k] + q) % MOD
for j in range(m):
    for k in range(len(positions) - 2, -1, -1):
        querySums[0][j][k] = (querySums[0][j][k] + querySums[0][j][k + 1]) % MOD
    for k in range(1, len(positions)):
        querySums[1][j][k] = (querySums[1][j][k] + querySums[1][j][k - 1]) % MOD
current_ans += pow(d + 1, n + 1, MOD)
current_ans %= MOD
_ = int(input())
for x in map(int, input().split()):
    ans = current_ans
    pos = -1
    (lo, hi) = (0, len(positions) - 1)
    while lo <= hi:
        mid = (lo + hi) // 2
        if positions[mid] >= x:
            pos = mid
            hi = mid - 1
        else:
            lo = mid + 1
    for j in range(m):
        if points[j] < x:
            total = querySums[0][j][pos]
            ans -= total
            ans += total * (x - points[j]) % MOD
            ans %= MOD
    pos = -1
    (lo, hi) = (0, len(positions) - 1)
    while lo <= hi:
        mid = (lo + hi) // 2
        if positions[mid] <= x:
            pos = mid
            lo = mid + 1
        else:
            hi = mid - 1
    for j in range(m):
        if x <= points[j]:
            total = querySums[1][j][pos]
            ans -= total
            ans += total * (points[j] - x) % MOD
            ans %= MOD
    print(ans)

Solution (Python):
input = __import__('sys').stdin.readline
MOD = 998244353
(d, n, m) = map(int, input().split())
lamps = list(sorted(map(int, input().split())))
points = list(sorted(map(int, input().split())))
positions = [x for x in points]
positions.append(0)
positions.append(d)
for i in range(m):
    for j in range(i + 1, m):
        mid = (points[i] + points[j]) // 2
        positions.append(mid)
        positions.append(mid + 1)
positions = list(sorted(set(positions)))
posmap = {x: i for (i, x) in enumerate(positions)}
i = 0
queryL = []
for p in points:
    queries = [0] * len(positions)
    while positions[i] < p:
        i += 1
    j = i
    q = 1
    for x in lamps:
        if x <= p:
            continue
        while x > positions[j]:
            queries[j] = q
            j += 1
        q = q * (x - p) % MOD
    while j < len(positions):
        queries[j] = q
        j += 1
    queryL.append(queries)
i = len(positions) - 1
queryR = []
for p in points[::-1]:
    queries = [0] * len(positions)
    while positions[i] > p:
        i -= 1
    j = i
    q = 1
    for x in lamps[::-1]:
        if x > p:
            continue
        while x < positions[j]:
            queries[j] = q
            j -= 1
        q = q * (p - x) % MOD
    while j >= 0:
        queries[j] = q
        j -= 1
    queryR.append(queries)
queryR = queryR[::-1]
querySums = [[[0] * len(positions) for _ in range(len(points))] for _ in range(2)]
current_ans = 0
for mask in range(1, 1 << m):
    keys = []
    prev_idx = -1
    popcnt = 0
    q = 1
    for i in range(m):
        if mask >> i & 1:
            p = points[i]
            if prev_idx == -1:
                keys.append((1, i, 0))
                q = q * queryR[i][0] % MOD
            else:
                prev_p = points[prev_idx]
                mid = (prev_p + p) // 2
                keys.append((0, prev_idx, posmap[mid]))
                q = q * queryL[prev_idx][posmap[mid]] % MOD
                keys.append((1, i, posmap[mid + 1]))
                q = q * queryR[i][posmap[mid + 1]] % MOD
            prev_idx = i
            popcnt += 1
    keys.append((0, prev_idx, len(positions) - 1))
    q = q * queryL[prev_idx][-1] % MOD
    if popcnt & 1:
        current_ans = (current_ans - q) % MOD
        for (i, j, k) in keys:
            querySums[i][j][k] = (querySums[i][j][k] - q) % MOD
    else:
        current_ans = (current_ans + q) % MOD
        for (i, j, k) in keys:
            querySums[i][j][k] = (querySums[i][j][k] + q) % MOD
for j in range(m):
    for k in range(len(positions) - 2, -1, -1):
        querySums[0][j][k] = (querySums[0][j][k] + querySums[0][j][k + 1]) % MOD
    for k in range(1, len(positions)):
        querySums[1][j][k] = (querySums[1][j][k] + querySums[1][j][k - 1]) % MOD
current_ans += pow(d + 1, n + 1, MOD)
current_ans %= MOD
_ = int(input())
for x in map(int, input().split()):
    ans = current_ans
    for i in range(len(positions)):
        if positions[i] >= x:
            pos = i
            break
    for j in range(m):
        if points[j] < x:
            total = querySums[0][j][pos]
            ans -= total
            ans += total * (x - points[j]) % MOD
            ans %= MOD
    for i in range(len(positions) - 1, -1, -1):
        if positions[i] <= x:
            pos = i
            break
    for j in range(m):
        if x <= points[j]:
            total = querySums[1][j][pos]
            ans -= total
            ans += total * (points[j] - x) % MOD
            ans %= MOD
    print(ans)

Solution (Python):
input = __import__('sys').stdin.readline
MOD = 998244353
(d, n, m) = map(int, input().split())
lamps = list(sorted(map(int, input().split())))
points = list(sorted(map(int, input().split())))
positions = [x for x in points]
positions.append(0)
positions.append(d)
for i in range(m):
    for j in range(i + 1, m):
        mid = (points[i] + points[j]) // 2
        positions.append(mid)
        positions.append(mid + 1)
positions = list(sorted(set(positions)))
posmap = {x: i for (i, x) in enumerate(positions)}
i = 0
queryL = []
for p in points:
    queries = [0] * len(positions)
    while positions[i] < p:
        i += 1
    j = i
    q = 1
    for x in lamps:
        if x <= p:
            continue
        while x > positions[j]:
            queries[j] = q
            j += 1
        q = q * (x - p) % MOD
    while j < len(positions):
        queries[j] = q
        j += 1
    queryL.append(queries)
i = len(positions) - 1
queryR = []
for p in points[::-1]:
    queries = [0] * len(positions)
    while positions[i] > p:
        i -= 1
    j = i
    q = 1
    for x in lamps[::-1]:
        if x > p:
            continue
        while x < positions[j]:
            queries[j] = q
            j -= 1
        q = q * (p - x) % MOD
    while j >= 0:
        queries[j] = q
        j -= 1
    queryR.append(queries)
queryR = queryR[::-1]
querySums = [[[0] * len(positions) for _ in range(len(points))] for _ in range(2)]
current_ans = 0
for mask in range(1, 1 << m):
    keys = []
    prev_idx = -1
    popcnt = 0
    q = 1
    for i in range(m):
        if mask >> i & 1:
            p = points[i]
            if prev_idx == -1:
                keys.append((1, i, 0))
                q = q * queryR[i][0] % MOD
            else:
                prev_p = points[prev_idx]
                mid = (prev_p + p) // 2
                keys.append((0, prev_idx, posmap[mid]))
                q = q * queryL[prev_idx][posmap[mid]] % MOD
                keys.append((1, i, posmap[mid + 1]))
                q = q * queryR[i][posmap[mid + 1]] % MOD
            prev_idx = i
            popcnt += 1
    keys.append((0, prev_idx, len(positions) - 1))
    q = q * queryL[prev_idx][-1] % MOD
    if popcnt & 1:
        current_ans = (current_ans - q) % MOD
        for (i, j, k) in keys:
            querySums[i][j][k] = (querySums[i][j][k] - q) % MOD
    else:
        current_ans = (current_ans + q) % MOD
        for (i, j, k) in keys:
            querySums[i][j][k] = (querySums[i][j][k] + q) % MOD
for j in range(m):
    for k in range(len(positions) - 2, -1, -1):
        querySums[0][j][k] = (querySums[0][j][k] + querySums[0][j][k + 1]) % MOD
    for k in range(1, len(positions)):
        querySums[1][j][k] = (querySums[1][j][k] + querySums[1][j][k - 1]) % MOD
current_ans += pow(d + 1, n + 1, MOD)
current_ans %= MOD
_ = int(input())
for x in map(int, input().split()):
    ans = current_ans
    for i in range(len(positions)):
        if positions[i] >= x:
            pos = i
            break
    for j in range(m):
        if points[j] < x:
            total = querySums[0][j][pos]
            ans -= total
            ans += total * (x - points[j]) % MOD
            ans %= MOD
    for i in range(len(positions) - 1, -1, -1):
        if positions[i] <= x:
            pos = i
            break
    for j in range(m):
        if x <= points[j]:
            total = querySums[1][j][pos]
            ans -= total
            ans += total * (points[j] - x) % MOD
            ans %= MOD
    print(ans)