Với một nhân viên ~x~, ta xét riêng những truy vấn đổi phòng của nhân viên thì nhận được danh sách đỉnh ~v_0 = a_x, v_1, v_2, \cdots, v_k~ với các thời điểm tương ứng là ~t_0 = 0, t_1, t_2, \cdots t_k~.

Ta giả sử ta chỉ cần tính hiệu suất của nhân viên ~i~ sau ~Q~ truy vấn, khi đó các hiệu xuất của nhân viên được tính bằng :

$$\sum_{i = 0}^k f_{v_i}(t_i, t_{i + 1}) - \sum_{i = 0}^{k - 1} dist(v_i, v_{i + 1})$$

Với ~t_k = Q + 1~, hàm ~f_u(l, r)~ là tổng các truy vấn thêm tiện ích vô đỉnh ~u~ trong các thời điểm ~t \in [l, r]~.

Giờ ta sẽ giải bài toán với ~q~ bất kỳ, ta tìm thời điểm ~t_j~ và đỉnh ~v_j~ cuối cùng nhân viên ~x~ đang ở bằng chặt nhị phân, sau đó phần tiền tố tính bằng Fenwick Tree/Segment Tree và ta chỉ cần tính thêm lại hàm ~f_{v_j}(t_j, q)~

Giờ khi ta chuyển từ nhân viên ~x~ sang nhân viên ~x+1~, sẽ có những sự kiện bị thay đổi và ta sẽ duy trì bằng Sweep line theo chỉ số nhân viên, dùng cấu trúc dữ liệu để duy trì thông tin truy vấn.

Với mỗi sự kiên thêm/xóa ta chỉ cần dùng Linked-List và xử lý bằng set/map là xong.

Độ phức tạp ~\mathcal{O}((N + Q) \log_2 (N))~