• What would you do if the constraints for the coordinates were up to (10^5)?

• You could use the line sweep algorithm, but the coordinates go up to (10^9). So, what shall we do?

• What if you use a dictionary instead of an array to store only the relevant positions?

We perform a line sweep using a dictionary to record events at positions where the number of covering segments changes. Sorting the dictionary keys lets us compute the prefix sum between these "critical" points. For each interval ([prev, cur)), the number of integer points is ((cur — prev)) and they are all covered by the current number of segments. This way, we aggregate the answer for every (k) in ([1, n]) without iterating over every integer in a huge range.

import sys
from collections import defaultdict

n = int(sys.stdin.readline().strip())
events = defaultdict(int)

# Record events: +1 when a segment starts, -1 when it ends (at r+1)
for _ in range(n):
    l, r = map(int, sys.stdin.readline().split())
    events[l] += 1
    events[r + 1] -= 1

# Sort the event points
keys = sorted(events.keys())
coverage = 0
prev = keys[0]
result = defaultdict(int)

# Line sweep: update coverage and count points in intervals
for point in keys:
    result[coverage] += point - prev
    coverage += events[point]
    prev = point

# Output counts for points covered by exactly 1 to n segments
ans = [result[k] for k in range(1, n + 1)]
print(*ans)
    

Let's consider a very special case of equal distances. What if all distances were equal to $$$1$$$? It implies that if some letter appears exactly twice, both occurrences are placed right next to each other.

That construction can be achieved if you sort the string, for example: first right down all letters '$$$a$$$', then all letters '$$$b$$$' and so on. If a letter appears multiple times, all its occurrences will be next to each other, just as we wanted.

Overall complexity: $$$O(|s|log|s|)$$$ or $$$O(|s|)$$$ per testcase.

for _ in range(int(input())):
  print(''.join(sorted(input())))

• Solution 1: Let's use the data structure called a bitwise trie. Fix some $$$a_{i}$$$, where all $$$a_{j}$$$ for $$$j<i$$$ have already been added to the trie. We will iterate over the bits in $$$a_{i}$$$ from the $$$(k−1)^{th}$$$ bit to the $$$0^{th}$$$ bit. Since $$$2^{t}>2^{t−1}+2^{t−2}+…+2+1$$$, if there exists $$$a_{j}$$$ with the same bit at the corresponding position in $$$a_{i}$$$, we will go into that branch of the trie and append $$$1−b$$$ to the corresponding bit $$$x$$$. Otherwise, our path is uniquely determined. When we reach a leaf, the bits on the path will correspond to the optimal number $$$a_{j}$$$ for $$$a_{i}$$$. The time complexity of this solution is $$$O(nk)$$$.
• Solution 2: Sort $$$a_{1},a_{2},…,a_{n}$$$ in non-decreasing order. We will prove that the answer is some pair of adjacent numbers. Let the answer be numbers $$$a_{i},a_{j} (j−i>1)$$$. If $$$a_{i}=a_{j}$$$, then $$$a_{i}=a_{i+1}$$$. Otherwise, they have a common prefix of bits, after which there is a differing bit. That is, at some position $$$t$$$, $$$a_{i}$$$ has a $$$0$$$ and $$$a_{j}$$$ has a $$$1$$$. Since $$$j−i>1$$$, $$$a{i+1}$$$ can have either $$$0$$$ or $$$1$$$ at this position, but in the first case it is more advantageous to choose $$$a_{i},a_{i+1}$$$ as the answer, and in the second case it is more advantageous to choose $$$a_{i+1},a_{j}$$$ as the answer. The complexity of this solution is $$$O(nlogn)$$$.

For the first approach, make sure to use $$$PyPy 3-64$$$.

import sys
input = lambda: sys.stdin.readline().rstrip()

class TrieNode:
    def __init__(self):
        self.children = [None, None]
        self.position = -1 # index of the corresponding number in the given array

t = int(input())
for _ in range(t):
    n, k = map(int, input().split())
    a = list(map(int, input().split()))

    ans_i = ans_j = ans_x = 1, 1, 0
    max_val = 0 # maximum value of (a[i] ^ x) & (a[j] ^ x)
    
    root_node = TrieNode()
    for i, num in enumerate(a):
        cur_node = root_node
        # find a pair a[j] for this number
        # first check if there's at least one number in the trie
        if cur_node.children[0] or cur_node.children[1]:
            x = 0
            for bit_i in range(k - 1, -1, -1):
                if num & (1 << bit_i):
                    # match 1 bit with 1 bit
                    if cur_node.children[1]:
                        cur_node = cur_node.children[1]
                    else: # if not possible, match 1 bit with 0 bit
                        cur_node = cur_node.children[0]

                else:
                    # match 0 bit with 0 bit
                    if cur_node.children[0]:
                        cur_node = cur_node.children[0]
                        x = x ^ (1 << bit_i)
                    else: # if not possible, match 0 bit with 1 bit
                        cur_node = cur_node.children[1]

            j = cur_node.position
            new_val = (num ^ x)&(a[j] ^ x)
            if new_val >= max_val:
                max_val = new_val
                ans_i, ans_j, ans_x = i + 1, j + 1, x

        # insert the current number into the trie
        cur_node = root_node
        for bit_i in range(k - 1, -1, -1):
            if num & (1 << bit_i):
                if not cur_node.children[1]:
                    cur_node.children[1] = TrieNode()
                cur_node = cur_node.children[1]

            else:
                if not cur_node.children[0]:
                    cur_node.children[0] = TrieNode()
                cur_node = cur_node.children[0]

        cur_node.position = i

    print(ans_i, ans_j, ans_x)