Overview

For each query, we compute the sum of “tied ranks” for employees within the specified coordinate range. The sum of ranks can be transformed into “a constant determined by the number of elements − the number of pairs with the same evaluation score,” reducing the problem to efficiently counting the number of “equal-value pairs” within an interval.

Analysis

1. The sum of ranks can be expressed using “equal-value pairs”

Let the set obtained by a query (actually a contiguous subarray of the array sorted by coordinates) consist of \(m\) people, with evaluation scores \(V_1,\dots,V_m\).

Each employee’s rank is: - \(k+1\), where \(k\) is the number of people with a strictly greater evaluation

So the sum of ranks is: [ \sum_{i=1}^{m} (1 + #{j: V_j > Vi}) = m + \sum{i=1}^{m} #{j: V_j > V_i} ]

Now, consider pairs \((i,j)\) with \(i<j\): - If \(V_i \neq V_j\), the one with the smaller value has “one more person greater than them,” so this pair contributes +1 to the sum - If \(V_i = V_j\), neither counts as “strictly greater,” so the contribution is 0

Therefore: [ \sum_{i=1}^{m} #{j: V_j > V_i} = \binom{m}{2} - (\text{number of equal-value pairs}) ] Thus: [ \text{sum of ranks} = m + \binom{m}{2} - (\text{number of equal-value pairs}) = \frac{m(m+1)}{2} - (\text{number of equal-value pairs}) ]

Therefore, each query reduces to: - \(m = r-l+1\) is known, so \(\frac{m(m+1)}{2}\) can be computed immediately - The remaining task is to count the number of pairs with the same evaluation score in the interval (e.g., if a value appears \(c\) times, it contributes \(\binom{c}{2}\))

2. A naive solution is too slow

If we extract the interval and count frequencies for each query, the worst case is \(O(N)\) per query: [ O(NQ) \approx 10^{10} ] which results in TLE.

3. Solution approach: efficiently compute equal-value pairs in intervals offline

Since all coordinates \(X_i\) are distinct, sorting employees by \(X\) allows us to convert each query \([L,R]\) into a contiguous array interval \([l,r]\) via binary search.

The remaining task is to efficiently process many interval queries on a static array to count equal-value pairs. The code uses an offline approach with sqrt decomposition (block partitioning), achieving roughly \(O((N+Q)\sqrt{N})\).

Algorithm

Overall Flow

1. Sort employees by work location coordinate \(X\) and create array V[0..N-1]
2. Convert each query \([L,R]\) to index interval \([l,r]\) using bisect_left/right
3. For each query, compute: [ m=r-l+1,\quad \text{total}=\frac{m(m+1)}{2} ] then find the number of equal-value pairs pairs and output total - pairs
4. Speed up computation of equal-value pairs by handling two cases:
   • Query within a single block: The length is \(\le S\), so count directly
   • Query spanning multiple blocks: Group by left-end block and process by extending the right endpoint

Preprocessing: Coordinate compression of evaluation scores

Evaluation scores \(V_i\) can be up to \(10^9\), so they cannot be used directly as frequency array indices. Create uniq = sorted(set(V)) and compress each \(V\) to 0..K-1 as A[i] (the mp and A in the code).

This allows using a frequency array cnt[0..K-1].

Update formula for equal-value pairs

When adding a value \(a\) to the interval, if there are already \(c\) occurrences of \(a\) in the interval, the number of new equal-value pairs is \(c\): - pairs += c - cnt[a] += 1

This maintains the number of equal-value pairs in the interval.

Case 1: Queries within a single block (short, handle directly)

Set block width \(S \approx \sqrt{N}\). If \(l\) and \(r\) are in the same block, the length is at most \(S\), so scan the interval to count frequencies and compute equal-value pairs.

To avoid the overhead of reinitializing cnt every time, the code uses: - tmp_vis and ver (version management) to “only reset values that were touched in this query.”

Case 2: Queries spanning multiple blocks (offline processing)

Group queries by left-end block lb = l//S, and sort queries with the same lb in ascending order of right endpoint r.

Let the right boundary of block b be midL = (b+1)*S, and maintain a base interval with: - Left endpoint fixed at midL - Right endpoint extended via cur_r

Processing steps (for each query \((l,r)\)): 1. Extend cur_r to r while updating cnt and pairs (adding the right side) 2. Temporarily add the left portion [l, midL-1] to obtain pairs 3. Remove the temporarily added left portion to restore the state (for the next query)

The temporary left addition is within block width \(S\), so it costs \(O(S)\) per query. The right endpoint extension totals \(O(N)\) across all queries within a block.

Finally, output: [ \text{answer} = \text{total} - \text{pairs} ]

Complexity

• Time complexity: approximately \(O\big((N+Q)\sqrt{N}\big)\)
  • Within a single block: \(O(S)\) per query
  • Spanning multiple blocks: total \(O(N)\) for right endpoint extension (per block), \(O(S)\) for left-side processing per query
• Space complexity: \(O(N + Q + K)\) (where \(K\) is the number of distinct evaluation scores, at most \(N\))

Implementation Notes

• Converting to query intervals: Sort employees by \(X\), then use l = bisect_left(X, L), r = bisect_right(X, R) - 1 (if empty, l > r).

• Answer formula: For interval length \(m\), compute total = m*(m+1)//2, and with equal-value pair count pairs, output total - pairs.

• Coordinate compression: Map V to 0..K-1 and manage with a frequency array.

• Optimization within a single block: Instead of reinitializing the entire cnt array each time, use tmp_vis + versioning to “only reset values that were touched.”

  Source Code

import sys
from bisect import bisect_left, bisect_right

def main():
    it = iter(map(int, sys.stdin.buffer.read().split()))
    N = next(it)
    Q = next(it)

    emp = []
    for _ in range(N):
        x = next(it)
        v = next(it)
        emp.append((x, v))
    emp.sort()

    X = [x for x, _ in emp]
    V = [v for _, v in emp]

    uniq = sorted(set(V))
    mp = {v: i for i, v in enumerate(uniq)}
    A = [mp[v] for v in V]
    K = len(uniq)

    S = int(N ** 0.5) + 1
    nb = (N + S - 1) // S

    queries_by_block = [[] for _ in range(nb)]
    ans = [0] * Q

    tmp_cnt = [0] * K
    tmp_vis = [0] * K
    ver = 0

    bl = bisect_left
    br = bisect_right

    for qi in range(Q):
        L = next(it)
        R = next(it)
        l = bl(X, L)
        r = br(X, R) - 1
        if l > r:
            ans[qi] = 0
            continue
        m = r - l + 1
        total = m * (m + 1) // 2
        lb = l // S
        rb = r // S
        if lb == rb:
            ver += 1
            cv = ver
            pairs = 0
            for idx in range(l, r + 1):
                a = A[idx]
                if tmp_vis[a] != cv:
                    tmp_vis[a] = cv
                    tmp_cnt[a] = 0
                c = tmp_cnt[a]
                pairs += c
                tmp_cnt[a] = c + 1
            ans[qi] = total - pairs
        else:
            queries_by_block[lb].append((r, l, qi, total))

    A_local = A
    for b in range(nb):
        qlist = queries_by_block[b]
        if not qlist:
            continue
        qlist.sort()
        midL = (b + 1) * S
        if midL > N:
            midL = N

        cnt = [0] * K
        pair = 0
        cur_r = midL - 1

        for r, l, qi, total in qlist:
            for idx in range(cur_r + 1, r + 1):
                a = A_local[idx]
                c = cnt[a]
                pair += c
                cnt[a] = c + 1
            cur_r = r

            for idx in range(midL - 1, l - 1, -1):
                a = A_local[idx]
                c = cnt[a]
                pair += c
                cnt[a] = c + 1

            pairs = pair

            for idx in range(l, midL):
                a = A_local[idx]
                c = cnt[a] - 1
                cnt[a] = c
                pair -= c

            ans[qi] = total - pairs

    sys.stdout.write("\n".join(map(str, ans)))

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.