Overview

This problem involves efficiently processing queries on a company organization represented as a rooted tree: updating employee salaries and counting the number of subordinates of a given employee whose salary is higher than that employee’s salary.

Approach

Converting Subtrees to Intervals

First, to efficiently handle “all subordinates of employee \(v\)”, we want to convert the tree structure into contiguous intervals on an array. This can be achieved using an Euler Tour.

By arranging employees in DFS visit order, the employees belonging to the subtree of employee \(v\) correspond to a contiguous interval \([\mathrm{tin}[v], \mathrm{tout}[v]]\) on the array. The subordinates (excluding \(v\) itself) correspond to the interval \([\mathrm{tin}[v]+1, \mathrm{tout}[v]]\).

Issues with the Naive Approach

If we scan all subordinates for each query 2, it takes \(O(N)\) in the worst case, resulting in \(O(NQ)\) for \(Q\) queries. When \(N, Q \leq 10^5\), this amounts to up to \(10^{10}\) operations, which will TLE.

Solving with Sqrt Decomposition

Since the problem can be reduced to counting the number of elements greater than a given value in an interval on an array, we apply Sqrt Decomposition.

We divide the array into blocks of size \(B \approx \sqrt{N}\) and also maintain a sorted list of elements within each block. This allows:

• Update: Remove the old value from the corresponding block’s sorted list and insert the new value → \(O(B)\)
• Range query: For fully contained blocks, use binary search in \(O(\log B)\); for partial blocks at the endpoints, use linear scan in \(O(B)\) → Overall \(O(\frac{N}{B} \log B + B)\)

Setting \(B = \sqrt{N}\), each query can be processed in approximately \(O(\sqrt{N} \log N)\).

Algorithm

1. Euler Tour Construction: Perform an iterative DFS rooted at employee \(1\), recording the entry time \(\mathrm{tin}[v]\) and exit time \(\mathrm{tout}[v]\) for each employee. Create an array euler_salary with salaries arranged in DFS order.

2. Sqrt Decomposition Initialization: Divide euler_salary into blocks of size \(B = 250\) or so, and create a sorted list blocks[b] of the values within each block.

3. Query Processing:

   • Update query 1 v x: Find the position of employee \(v\) in the Euler Tour, update the value in euler_salary. Remove the old value from the corresponding block’s sorted list and insert the new value.
   • Investigation query 2 v: For the subordinate interval \([l, r] = [\mathrm{tin}[v]+1, \mathrm{tout}[v]]\), count the number of elements strictly greater than \(A[v]\). For complete blocks, use bisect_right for binary search; for partial blocks at the endpoints, use linear scan.

Complexity

• Time complexity: \(O(N \log N + Q \cdot (\sqrt{N} \log N + \sqrt{N}))\) (each query is approximately \(O(\sqrt{N} \log N)\); updates are \(O(\sqrt{N})\))
• Space complexity: \(O(N)\)

Implementation Notes

• Implementing Euler Tour with iterative DFS: For \(N \leq 10^5\), recursive DFS in Python hits the stack limit, so we use an explicit stack for iterative processing.

• Updating the sorted list: Find the position of the old value using bisect_right(block, old_val - 1) and pop it, then use insort to insert the new value. This allows updates in \(O(B)\).

• Case when there are 0 subordinates: When \(l > r\), immediately output 0 (e.g., for leaf nodes).

• Block size selection: \(B = 250\) or so works well in practice. Since Python has large constant factors, it is important to use binary search for complete blocks to achieve speedup.

  Source Code

import sys
from bisect import bisect_right, insort

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    Q = int(input_data[idx]); idx += 1
    
    A = [0] * (N + 1)
    for i in range(1, N + 1):
        A[i] = int(input_data[idx]); idx += 1
    
    children = [[] for _ in range(N + 1)]
    for i in range(2, N + 1):
        p = int(input_data[idx]); idx += 1
        children[p].append(i)
    
    # Euler tour to get subtree ranges
    tin = [0] * (N + 1)
    tout = [0] * (N + 1)
    order = []  # euler tour order
    
    # Iterative DFS for Euler tour
    timer = 0
    stack = [(1, False)]
    while stack:
        node, visited = stack.pop()
        if visited:
            tout[node] = timer - 1
        else:
            tin[node] = timer
            timer += 1
            order.append(node)
            stack.append((node, True))
            for c in reversed(children[node]):
                stack.append((c, False))
    
    # For N, Q <= 5*10^4, we can use sqrt decomposition
    # Block size for sqrt decomposition on the Euler tour array
    # Each block maintains a sorted list of salary values
    
    BLOCK = 250  # sqrt(50000) ~ 224, use 250
    num_blocks = (N + BLOCK - 1) // BLOCK
    
    # euler[i] = salary of the node at position i in euler tour
    euler_salary = [0] * N
    euler_node = [0] * N  # which node is at position i
    node_pos = [0] * (N + 1)  # position of node in euler tour
    
    for i in range(N):
        node = order[i]
        euler_salary[i] = A[node]
        euler_node[i] = node
        node_pos[node] = i
    
    # Build sorted blocks
    blocks = []
    for b in range(num_blocks):
        start = b * BLOCK
        end = min(start + BLOCK, N)
        sorted_block = sorted(euler_salary[start:end])
        blocks.append(sorted_block)
    
    def update(node, new_val):
        pos = node_pos[node]
        old_val = euler_salary[pos]
        euler_salary[pos] = new_val
        A[node] = new_val
        b = pos // BLOCK
        # Remove old_val and insert new_val in sorted block
        block = blocks[b]
        # Find and remove old_val
        lo = bisect_right(block, old_val - 1)
        # block[lo] should be old_val
        # Use index to find exact position
        block.pop(lo)
        insort(block, new_val)
    
    def count_greater(l, r, val):
        # Count elements strictly greater than val in euler_salary[l..r]
        if l > r:
            return 0
        result = 0
        lb = l // BLOCK
        rb = r // BLOCK
        
        if lb == rb:
            # Same block, brute force
            for i in range(l, r + 1):
                if euler_salary[i] > val:
                    result += 1
            return result
        
        # Left partial block
        left_end = (lb + 1) * BLOCK - 1
        for i in range(l, left_end + 1):
            if euler_salary[i] > val:
                result += 1
        
        # Full blocks
        for b in range(lb + 1, rb):
            block = blocks[b]
            # Count elements > val
            pos = bisect_right(block, val)
            result += len(block) - pos
        
        # Right partial block
        right_start = rb * BLOCK
        for i in range(right_start, r + 1):
            if euler_salary[i] > val:
                result += 1
        
        return result
    
    out = []
    for _ in range(Q):
        t = int(input_data[idx]); idx += 1
        if t == 1:
            v = int(input_data[idx]); idx += 1
            x = int(input_data[idx]); idx += 1
            update(v, x)
        else:
            v = int(input_data[idx]); idx += 1
            # Subtree of v: positions tin[v] to tout[v]
            # Descendants only: tin[v]+1 to tout[v]
            l = tin[v] + 1
            r = tout[v]
            if l > r:
                out.append('0')
            else:
                val = A[v]
                ans = count_greater(l, r, val)
                out.append(str(ans))
    
    sys.stdout.write('\n'.join(out) + '\n')

main()

---

This editorial was generated by claude4.6opus-thinking.