Overview

This problem involves a company organization represented as a tree structure, where we need to efficiently process queries that update each employee’s salary and count the number of subordinates of a specified employee whose salary is greater than that employee’s salary.

Analysis

The core operations of the problem are the following two points: 1. Updating an employee’s salary 2. Counting the number of subordinates of a given employee whose salary is greater than that employee’s salary

In a naive approach, scanning all subordinates and comparing salaries for each type-2 query results in \(O(NQ)\) in the worst case, which is too slow given the constraints \(N, Q \leq 10^5\).

For efficient processing, the following observations are important: - By traversing the tree in DFS order (Euler tour), all subordinates of each employee can be represented as a contiguous interval - Query 2 can be reduced to the problem of “counting the number of elements greater than value \(x\) within interval \([l, r]\)” - To process interval queries efficiently, we use square root decomposition and maintain sorted buckets instead of balanced binary search trees

Algorithm

1. Euler Tour: Using DFS, we record the entry time (in_time) and exit time (out_time) for each node. This way, all subordinates of employee \(v\) correspond to the contiguous interval \([in\_time[v]+1, out\_time[v]]\) on the array.

2. Square Root Decomposition: We divide the array into buckets of size approximately \(\sqrt{N}\), and maintain the values within each bucket in sorted order.

3. Update Processing: When updating a salary, we delete the old value from the corresponding bucket and insert the new value. Buckets are always kept in sorted order.

4. Query Processing: For interval queries, we use binary search on fully contained buckets to count the number of elements greater than \(x\), and directly scan partial intervals.

Complexity

• Time complexity: \(O(Q\sqrt{N}\log N)\)
  • Update processing: \(O(\sqrt{N}\log N)\) (bucket deletion and insertion)
  • Query processing: \(O(\sqrt{N}\log N)\) (binary search on buckets and partial scanning)
• Space complexity: \(O(N)\)

Implementation Notes

• The Euler tour is implemented with non-recursive DFS to prevent stack overflow

• The bucket size is set to \(\sqrt{N}\) to balance the computational complexity

• The bisect module is used for efficient insertion and deletion in buckets

• Care must be taken with boundary cases (such as empty intervals) when processing partial intervals

  Source Code

import sys
import math
import bisect

def main():
    data = sys.stdin.read().split()
    if not data:
        return
    
    it = iter(data)
    n = int(next(it)); q = int(next(it))
    A = [0] * (n+1)
    for i in range(1, n+1):
        A[i] = int(next(it))
    
    graph = [[] for _ in range(n+1)]
    for i in range(2, n+1):
        p = int(next(it))
        graph[p].append(i)
    
    in_time = [0] * (n+1)
    out_time = [0] * (n+1)
    time = 0
    stack = [1]
    while stack:
        u = stack.pop()
        if u > 0:
            time += 1
            in_time[u] = time
            stack.append(-u)
            for v in reversed(graph[u]):
                stack.append(v)
        else:
            u = -u
            out_time[u] = time

    arr = [0] * (n+1)
    for i in range(1, n+1):
        arr[in_time[i]] = A[i]
    
    size = int(math.isqrt(n)) + 1
    bucket_count = (n + size) // size
    buckets = [[] for _ in range(bucket_count)]
    for i in range(1, n+1):
        idx_b = (i-1) // size
        buckets[idx_b].append(arr[i])
    
    for i in range(bucket_count):
        buckets[i].sort()
    
    def update(pos, old_val, new_val):
        idx_b = (pos-1) // size
        arr[pos] = new_val
        bucket = buckets[idx_b]
        # Remove old_val
        pos_in_bucket = bisect.bisect_left(bucket, old_val)
        del bucket[pos_in_bucket]
        # Insert new_val
        bisect.insort(bucket, new_val)
    
    def query(l, r, x):
        res = 0
        left_b = (l-1) // size
        right_b = (r-1) // size
        if left_b == right_b:
            for i in range(l, r+1):
                if arr[i] > x:
                    res += 1
        else:
            for i in range(l, min((left_b+1)*size+1, n+1)):
                if arr[i] > x:
                    res += 1
            for b in range(left_b+1, right_b):
                bucket = buckets[b]
                cnt = len(bucket) - bisect.bisect_right(bucket, x)
                res += cnt
            for i in range(right_b*size+1, r+1):
                if arr[i] > x:
                    res += 1
        return res

    output_lines = []
    for _ in range(q):
        t = next(it)
        if t == '1':
            v = int(next(it)); x = int(next(it))
            pos = in_time[v]
            old_val = arr[pos]
            update(pos, old_val, x)
        else:
            v = int(next(it))
            l = in_time[v] + 1
            r = out_time[v]
            if l > r:
                output_lines.append("0")
            else:
                x = arr[in_time[v]]
                cnt = query(l, r, x)
                output_lines.append(str(cnt))
    
    sys.stdout.write("\n".join(output_lines))

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.