Hướng dẫn cho Quản lý lương (C.P.VNOI 2021 LMH R10)


Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Tóm tắt đề bài

Cho một công ty có \(n\) nhân viên với cấu trúc phân cấp dạng cây, trong đó nhân viên 1 là Tổng giám đốc (gốc của cây). Mỗi nhân viên \(i\) có một mức lương khởi điểm \(w_i\). Một người \(A\) quản lý người \(B\) nếu \(A\) là tổ tiên của \(B\) trên cây sơ đồ tổ chức.
Có hai loại truy vấn:

  1. p A x: Tăng lương của tất cả những người thuộc quyền quản lý của \(A\) (các nút thuộc cây con gốc \(A\)) thêm \(x\) đơn vị.
  2. u A: In ra mức lương hiện tại của người \(A\).

Phân tích

  • Cấu trúc dữ liệu: Cấu trúc quản lý của công ty là một cây có gốc tại nút 1.
  • Thao tác trên cây con: Truy vấn loại p yêu cầu cập nhật giá trị trên toàn bộ một cây con. Truy vấn loại u yêu cầu lấy giá trị tại một nút đơn lẻ.
  • Ràng buộc: \(n, m \leq 10^5\), lương có thể lên tới \(10^{18}\) và giá trị tăng thêm \(x\) có thể âm. Do đó, ta cần sử dụng kiểu dữ liệu long long.
  • Kỹ thuật: Để xử lý các thao tác trên cây con một cách hiệu quả, ta có thể sử dụng kỹ thuật trải phẳng cây (Euler Tour) kết hợp với các cấu trúc dữ liệu quản lý đoạn như Segment Tree hoặc Fenwick Tree.

Hướng giải quyết

1. Trải phẳng cây (Euler Tour)

Sử dụng thuật toán DFS để duyệt cây và đánh số lại các nút. Với mỗi nút \(u\), ta lưu lại hai giá trị:

  • fi[u]: Thời điểm bắt đầu thăm nút \(u\).
  • se[u]: Thời điểm kết thúc thăm tất cả các nút trong cây con gốc \(u\).

Khi đó, toàn bộ các nút thuộc cây con gốc \(u\) sẽ nằm trong đoạn liên tiếp từ fi[u] đến se[u] trên mảng đã trải phẳng.

2. Cấu trúc dữ liệu Segment Tree

Sau khi trải phẳng cây, bài toán trở thành:

  • Truy vấn p A x: Cập nhật cộng thêm \(x\) vào đoạn \([fi[A], se[A]]\).
  • Truy vấn u A: Lấy giá trị tại vị trí \(fi[A]\).

Để thực hiện cập nhật đoạn và truy vấn điểm, ta sử dụng Segment Tree với Lazy Propagation:

  • Hàm update(id, l, r, u, v, val): Cộng val vào các nút thuộc đoạn \([u, v]\).
  • Hàm get(id, l, r, pos): Truy xuất giá trị tại vị trí pos.
  • Lưu ý: Lương cuối cùng của nhân viên \(A\) sẽ bằng: lương_khởi_điểm[A] + giá_trị_tăng_thêm_từ_Segment_Tree.

3. Các bước thực hiện

  1. Xây dựng danh sách kề biểu diễn cây từ dữ liệu vào.
  2. Chạy DFS từ gốc 1 để xác định các khoảng [fi[u], se[u]] cho từng nút \(u\).
  3. Khởi tạo Segment Tree (ban đầu tất cả bằng 0 vì ta chỉ quản lý phần lương thay đổi).
  4. Với mỗi truy vấn:
    • Nếu là p A x: Gọi update(fi[A], se[A], x).
    • Nếu là u A: Gọi get(fi[A]) và cộng thêm mức lương ban đầu \(a[A]\).

Độ phức tạp

  • Thời gian:
    • DFS: \(O(n)\)
    • Mỗi truy vấn p hoặc u: \(O(\log n)\)
    • Tổng cộng: \(O(n + m \log n)\)
  • Bộ nhớ: \(O(n)\) để lưu cây và Segment Tree.

Code tham khảo

C++
#include <bits/stdc++.h>
using namespace std;

// Sử dụng long long để tránh tràn số vì lương có thể rất lớn
#define int long long

const int N = 1e5 + 5;
int n, m;
int a[N], pos[N];
int fi[N], se[N];
vector<int> b, child[N];

// Hàm DFS để trải phẳng cây (Euler Tour)
void dfs(int u) {
    b.push_back(u);
    fi[u] = b.size(); // Thời điểm bắt đầu thăm u
    for (int v : child[u])
        dfs(v);
    se[u] = b.size(); // Thời điểm kết thúc thăm cây con gốc u
}

int seg[N * 4], lazy[N * 4];

// Kỹ thuật Lazy Propagation để cập nhật đoạn
void pushdown(int id, int l, int r) {
    if (lazy[id] == 0) return;
    int mid = (l + r) >> 1;

    // Cập nhật giá trị cho các nút con
    seg[id << 1] += lazy[id] * (mid - l + 1);
    seg[id << 1 | 1] += lazy[id] * (r - mid);

    // Đẩy giá trị lazy xuống các nút con
    lazy[id << 1] += lazy[id];
    lazy[id << 1 | 1] += lazy[id];

    lazy[id] = 0;
}

void update(int id, int l, int r, int u, int v, int val) {
    if (r < u || l > v) return;
    if (u <= l && r <= v) {
        seg[id] += (r - l + 1) * val;
        lazy[id] += val;
        return;
    }
    int mid = (l + r) >> 1;
    pushdown(id, l, r);
    update(id << 1, l, mid, u, v, val);
    update(id << 1 | 1, mid + 1, r, u, v, val);
    seg[id] = seg[id << 1] + seg[id << 1 | 1];
}

int get(int id, int l, int r, int p) {
    if (l == r) return seg[id];
    pushdown(id, l, r);
    int mid = (l + r) >> 1;
    if (p <= mid) return get(id << 1, l, mid, p);
    else return get(id << 1 | 1, mid + 1, r, p);
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);

    cin >> n >> m;
    // Nhập lương người 1
    cin >> a[1];
    // Nhập lương và thủ trưởng của những người còn lại
    for (int i = 2; i <= n; ++i) {
        int p; 
        cin >> a[i] >> p;
        child[p].push_back(i);
    }

    // Trải phẳng cây
    b.push_back(0); // Dummy index
    dfs(1);

    // pos[x] lưu vị trí của nút x trong mảng đã trải phẳng
    for (int i = 1; i <= n; ++i) pos[b[i]] = i;

    while (m--) {
        char ty; cin >> ty;
        if (ty == 'p') {
            int node, val; cin >> node >> val;
            // Cập nhật lương cho toàn bộ cây con gốc 'node'
            // Khoảng trong mảng trải phẳng là [fi[node], se[node]]
            update(1, 1, n, fi[node], se[node], val);
        }
        else {
            int x; cin >> x;
            // Lương hiện tại = Lương gốc + Lượng thay đổi từ Segment Tree
            cout << get(1, 1, n, pos[x]) + a[x] << '\n';
        }
    }
    return 0;
}

Bình luận

Mới nhất
Tải bình luận...

Không có bình luận nào.