Chọn Đội tuyển HSGQG TPHCM 2025 - Hiệu suất nhân viên

Xem dạng PDF
Gửi bài giải
Điểm: 0,01 (OI)
Giới hạn thời gian: 2.0s
Giới hạn bộ nhớ: 1G
Input: hsnv.inp
Output: hsnv.out
Tác giả:
bedao
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Một công ty có ~N~ phòng, kết nối với nhau bằng ~N-1~ hành lang nội bộ có thể di chuyển theo hai chiều sao cho một hành lang nối trực tiếp hai phòng và giữa hai phòng bất kỳ luôn có đường đi đến nhau.

Công ty có ~M~ nhân viên, ban đầu mỗi nhân viên làm việc tại một phòng nhất định. Một phòng có thể có nhiều nhân viên. Phòng, hành lang và nhân viên đều được đánh chỉ số bằng các số nguyên liên tiếp nhau, bắt đầu từ ~1~.

Mỗi nhân viên có một chỉ số hiệu suất cá nhân, ban đầu bằng ~0~.

Khi phòng ~X~ được bổ sung tiện ích, hiệu suất của tất cả nhân viên hiện đang làm việc tại phòng ~X~ tăng thêm ~V~ đơn vị.

Khi một nhân viên bị điều chuyển từ phòng ~A~ qua phòng ~B~, hiệu suất của nhân viên đó giảm đi ~K~ đơn vị, với ~K~ là độ dài quãng đường ngắn nhất từ phòng ~A~ đến phòng ~B~ (tính bằng số hành lang).

Hãy cho biết hiệu suất làm việc của một nhân viên trong quá trình công ty thực hiện việc trang bị tiện ích cho các phòng và điều chuyển nhân viên giữa các phòng.

Input

Vào từ file văn bản HSNV.INP:

  • Dòng đầu gồm ba số nguyên ~N~, ~M~, ~Q~ (~2 \le N \le 2 \cdot 10^5~, ~1 \le M, Q \le 2 \cdot 10^5~) lần lượt là số phòng, số nhân viên, số yêu cầu.
  • Dòng thứ hai gồm ~M~ số nguyên ~a_1, a_2, \ldots, a_M~, trong đó ~a_i~ là phòng mà nhân viên ~i~ ban đầu làm việc (~1 \le a_i \le N~).
  • ~N-1~ dòng tiếp theo, mỗi dòng gồm hai số nguyên ~u, v~ (~1 \le u, v \le N~, ~u \ne v~), cho biết có một hành lang nối trực tiếp giữa phòng ~u~ và phòng ~v~.
  • ~Q~ dòng tiếp theo mô tả các yêu cầu, thuộc một trong ba dạng sau:
    • e X V: phòng ~X~ được bổ sung tiện ích, tăng thêm ~V~ đơn vị hiệu suất cho tất cả nhân viên hiện đang làm việc tại phòng đó (~1 \le X \le N~, ~0 \le V \le 10^9~).
    • t L R Z: tất cả nhân viên có chỉ số từ ~L~ đến ~R~ đồng loạt được chuyển về phòng ~Z~ (~1 \le L \le R \le M~, ~1 \le Z \le N~).
    • q K: truy vấn hiệu suất hiện tại của nhân viên ~K~ (~1 \le K \le M~).

Đảm bảo có ít nhất một yêu cầu dạng q.

Output

Ghi ra file văn bản HSNV.OUT:

  • Với mỗi yêu cầu dạng q K, in ra một số nguyên trên một dòng là hiệu suất hiện tại của nhân viên ~K~.

Scoring

Subtask Điểm Giới hạn
1 ~20\%~ ~N, M, Q \le 2 \cdot 10^3~.
2 ~20\%~ ~N, M, Q \le 2 \cdot 10^4~.
3 ~60\%~ Không có ràng buộc nào thêm.

Sample Input 1

3 2 5
1 2
1 2
2 3
q 1
e 2 5
q 2
t 1 1 3
q 1

Sample Output 1

0
5
-2

Bình luận

Hãy đọc nội quy trước khi bình luận.


  • 0
    dragon3012009  đã bình luận lúc 22, Tháng 4, 2026, 17:00 ← sửa 2

    link

    Bài tương tự


  • 5
    nahn  đã bình luận lúc 15, Tháng 4, 2026, 1:52

    Solution

    Ta viết hiệu suất hiện tại của nhân viên i dưới dạng val(i) = base[i] + bonus[cur(i)].

    • bonus[x] là tổng tất cả truy vấn e x v
    • cur(i) là phòng hiện tại của nhân viên i
    • base[i] là phần còn lại

    Vì vậy với truy vấn e x v, ta chỉ cần cập nhật bonus[x] += v.

    Với truy vấn t L R Z, giả sử một nhân viên đang ở phòng A, trước khi chuyển có giá trị base[i] + bonus[A].
    Sau khi chuyển sang Z, hiệu suất giảm dist(A, Z), nên giá trị mới là base[i] + bonus[A] - dist(A, Z).

    Nhưng sau này ta vẫn muốn truy vấn theo công thức base'[i] + bonus[Z], nên:

    base'[i] + bonus[Z] = base[i] + bonus[A] - dist(A, Z)

    suy ra:

    base'[i] = base[i] + bonus[A] - bonus[Z] - dist(A, Z)

    Vậy nếu một đoạn nhân viên đang cùng ở phòng A được chuyển sang Z, ta chỉ cần cộng vào base của cả đoạn lượng:

    bonus[A] - bonus[Z] - dist(A, Z)

    Đây là kiểu range add, point query, nên ta dùng Fenwick Tree.

    Ta không lưu phòng hiện tại của từng nhân viên riêng lẻ, mà lưu các đoạn liên tiếp cùng phòng trong một set dưới dạng [l, r] -> room.

    Khi có truy vấn t L R Z, ta dùng hàm split(pos) để tách đoạn tại L và R + 1, nhờ đó mọi đoạn giao với [L, R] trở thành các phần tử riêng trong set.
    Lưu ý phải gọi theo thứ tự:

    auto R = split(r + 1);
auto L = split(l);

    để tránh làm hỏng iterator.

    Sau đó duyệt các đoạn trong [L, R]. Với mỗi đoạn [l, r] đang ở phòng A, ta cộng vào Fenwick:

    delta = bonus[A] - bonus[Z] - dist(A, Z)

    rồi xóa các đoạn cũ và chèn lại đúng một đoạn mới [L, R] -> Z.

    Khoảng cách giữa hai phòng được tính bằng LCA:

    dist(u, v) = h[u] + h[v] - 2 * h[lca(u, v)]

    Ta tiền xử lý LCA bằng binary lifting.

    Độ phức tạp
    • Tiền xử lý LCA: O(N log N)
    • Truy vấn e: O(1)
    • Truy vấn q: O(log M)
    • Truy vấn t: hiểu cơ bản là ban đầu có tối đa M đoạn, mỗi lần split chỉ tăng tối đa 2 đoạn, nên tổng số đoạn từng xuất hiện không thể vượt quá M + 2Q

    Tổng thể đủ AC với N, M, Q <= 2 * 10^5.

    Code tham khảo: Link


  • -4
    k32chanhung  đã bình luận lúc 14, Tháng 4, 2026, 1:58

    cho bo xin 1 downvote