• 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())))

We have an array ( a ) of length ( n ) and must answer ( q ) queries. Each query modifies all elements in a given range ( [l, r] ) by setting them to ( k ) and asks whether the sum of the updated array is odd.

Each query is independent, meaning changes do not persist for subsequent queries.

Observe that changing a subarray to a fixed value (k) affects the total sum in a predictable way. The effect on the total sum can be computed by removing the sum of the existing subarray and adding the contribution of the new values.

How can prefix sum help us here?

1. Compute the initial sum of the array.
2. Compute the prefix sum for quick range sum retrieval.
3. For each query:
   • Compute the sum of the range ( [l, r] ).
   • Replace it with ( (r — l + 1) \times k ).
   • Check if the new sum is odd.
   • Print "YES" if odd, else "NO".

```python import sys t = int(input())

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

prefix = [0] * (n + 1)
for i in range(n):
    prefix[i + 1] = prefix[i] + a[i]

total_sum = prefix[-1]
results = []
for _ in range(q):
    l, r, k = map(int, input().split())
    replaced_range_old_sum = prefix[r] - prefix[l - 1]
    replaced_range_new_sum = (r - l + 1) * k
    new_sum = total_sum - replaced_range_old_sum + replaced_range_new_sum

    if new_sum % 2 == 1:
        results.append("YES")
    else:
        results.append("NO")

sys.stdout.write("\n".join(results) + "\n")

```

• Computing the total sum: ( O(n) )
• Computing the prefix sum: ( O(n) )
• Each query: ( O(1) ) (using prefix sum)
• Total complexity: ( O(n + q) ) per test case, which is optimal given constraints.