Overview

This problem asks us to find the sum of ranks of employees within a specified work location range. We mathematically rephrase the definition of rank, reduce the problem to “counting pairs of employees with the same evaluation score,” and then efficiently process queries using Mo’s algorithm (square root decomposition).

Analysis

1. Issues with the Naive Approach

For each query, if we retrieve the employees within the range, sort them by evaluation score, and compute their ranks, it takes \(O(N \log N)\) per query. Since the number of queries \(Q\) can be up to \(10^5\), the total complexity becomes \(O(QN \log N)\), which exceeds the time limit (TLE).

2. Rephrasing the Sum of Ranks

To efficiently compute ranks, let’s rephrase the definition of rank. Let \(M\) be the number of employees within the range. An employee’s rank is “\(1 + (\text{number of employees with a strictly higher score})\).” Therefore, the sum of ranks of all employees within the range is:

\[ \text{Sum of ranks} = \sum_{i=1}^{M} \left( 1 + (\text{number of employees with a strictly higher score}) \right) \]

\[ = M + \sum_{i=1}^{M} (\text{number of employees with a strictly higher score}) \]

Here, the right-hand side \(\sum (\text{number of employees with a strictly higher score})\) is exactly equal to “the number of pairs of employees with different scores.” Furthermore, “the number of pairs with different scores” equals “the total number of pairs” minus “the number of pairs with the same score.” Since the total number of pairs is \(\frac{M(M-1)}{2}\), the formula transforms to:

\[ \text{Sum of ranks} = M + \frac{M(M-1)}{2} - (\text{number of pairs with the same score}) \]

\[ = \frac{M(M+1)}{2} - (\text{number of pairs with the same score}) \]

Verification with a concrete example: For \(3\) employees with scores \(5, 5, 3\) (\(M=3\)): - \(\frac{M(M+1)}{2} = \frac{3 \times 4}{2} = 6\) - The only pair with the same score is the \(1\) pair of the two employees with score \(5\). - Therefore, the sum of ranks is \(6 - 1 = 5\), which matches the example in the problem statement.

3. Efficient Processing of Range Queries

With the above rephrasing, what we need to compute for each query is only “the number of pairs with the same score within the range.” When extending or shrinking the interval by one position, if a score \(v\) is added or removed, the change in the number of pairs equals the “current count of score \(v\) in the interval.” This can be computed in \(O(1)\). Since queries can be read in advance and interval extensions/shrinks take \(O(1)\), Mo’s algorithm is extremely effective.

Algorithm

1. Preprocessing (Sorting and Coordinate Compression)
   • Sort employees in ascending order of their work location coordinate \(X_i\).
   • Since the range of evaluation scores \(V_i\) can be large, apply coordinate compression (convert to consecutive integers starting from \(0\)) so they can be used as array indices.
2. Query Transformation
   • Convert each query’s range \([L_j, R_j]\) into an index interval \([l, r)\) in the sorted employee array using binary search (bisect_left, bisect_right).
3. Applying Mo’s Algorithm
   • Reorder queries based on square root decomposition. Set the block size to \(B = \frac{N}{\sqrt{Q}}\), sort by the block number that the left endpoint \(l\) belongs to, and within the same block, sort by the right endpoint \(r\).
   • Maintain as state the “occurrence count of each score count” and the “current number of same-score pairs current_ans.”
   • Process queries in sorted order, extending or shrinking the left and right endpoints one step at a time from the current interval to the target interval, updating count and current_ans in \(O(1)\).
4. Computing the Answer
   • Using current_ans at the point each query is processed, compute \(\frac{M(M+1)}{2} - \text{current\_ans}\) and record it as the answer.

Complexity

• Time Complexity: \(O(N \sqrt{Q} + N \log N + Q \log Q)\)
  • Coordinate compression and sorting employees: \(O(N \log N)\).
  • Binary search and sorting for queries: \(O(Q \log N + Q \log Q)\).
  • The total number of interval extensions/shrinks by Mo’s algorithm is \(O(N \sqrt{Q})\). Each operation is \(O(1)\).
  • Therefore, the overall complexity is \(O(N \sqrt{Q} + N \log N + Q \log Q)\), which is sufficiently fast.
• Space Complexity: \(O(N + Q)\)
  • Memory is needed to store employee data, query data, count arrays, etc.

Implementation Notes

• Optimization of Mo’s Algorithm Sort Order When sorting queries, if the block number of the left endpoint is even, the right endpoint \(r\) is sorted in ascending order; if odd, in descending order (return (b, r) if b % 2 == 0 else (b, -r)). This prevents the right pointer from making large jumps back and forth at block boundaries, reducing total movement distance and improving the constant factor.

• Optimization in Python To reduce function call overhead, the interval extension/shrink operations (equivalent to add and remove) are written directly inside the while loops instead of being factored out into separate functions.

  Source Code

import sys
from bisect import bisect_left, bisect_right

def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    Q = int(input_data[1])
    
    employees = []
    idx = 2
    for _ in range(N):
        x = int(input_data[idx])
        v = int(input_data[idx+1])
        employees.append((x, v))
        idx += 2
        
    employees.sort(key=lambda item: item[0])
    
    X = [item[0] for item in employees]
    V_raw = [item[1] for item in employees]
    
    unique_V = list(set(V_raw))
    unique_V.sort()
    v_dict = {val: i for i, val in enumerate(unique_V)}
    V = [v_dict[v] for v in V_raw]
    
    queries = []
    for i in range(Q):
        L = int(input_data[idx])
        R = int(input_data[idx+1])
        idx += 2
        
        l = bisect_left(X, L)
        r = bisect_right(X, R)
        
        queries.append((l, r, i))
        
    B = max(1, int(N / (Q ** 0.5)))
    
    def sort_key(q):
        l, r, i = q
        b = l // B
        return (b, r) if b % 2 == 0 else (b, -r)
        
    queries.sort(key=sort_key)
    
    ans_list = [0] * Q
    
    count = [0] * len(unique_V)
    current_ans = 0
    
    curr_l = 0
    curr_r = 0
    
    for l, r, i in queries:
        if l >= r:
            ans_list[i] = 0
            continue
            
        while curr_l > l:
            curr_l -= 1
            v = V[curr_l]
            current_ans += count[v]
            count[v] += 1
            
        while curr_r < r:
            v = V[curr_r]
            current_ans += count[v]
            count[v] += 1
            curr_r += 1
            
        while curr_l < l:
            v = V[curr_l]
            count[v] -= 1
            current_ans -= count[v]
            curr_l += 1
            
        while curr_r > r:
            curr_r -= 1
            v = V[curr_r]
            count[v] -= 1
            current_ans -= count[v]
            
        M = r - l
        ans_list[i] = M * (M + 1) // 2 - current_ans
        
    sys.stdout.write('\n'.join(map(str, ans_list)) + '\n')

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3.1-pro-thinking.