Đề bài

Có \(N\) tháp quan sát, đánh số từ \(0\) đến \(N-1\). Tháp \(i\) có chiều cao \(H[i]\) và điểm quan sát \(S[i]\), ban đầu \(S[i]=0\).

Với \(0\le i<j\le N-1\), tháp \(j\) nhìn thấy được từ tháp \(i\) nếu

Các tháp có chỉ số không lớn hơn \(i\) không nhìn thấy được từ tháp \(i\). Khi quan sát từ một tháp, điểm \(S[j]\) của mọi tháp nhìn thấy được tăng thêm \(1\).

Có \(Q\) sự kiện, mỗi sự kiện thuộc một trong ba loại và được biểu diễn bằng một mảng có độ dài tương ứng:

• Quan sát [I]: quan sát từ tháp \(I\), với \(0\le I\le N-2\).
• Đo đạc [L, R]: tính \(S[L]+S[L+1]+\cdots+S[R]\).
• Biến động địa chất [L, R, V]: cộng \(V\) vào chiều cao của mọi tháp từ \(L\) đến \(R\).

Gọi \(K\) là tổng số sự kiện đo đạc. Hãy trả về kết quả của \(K\) lần đo theo đúng thứ tự xuất hiện.

Yêu cầu cài đặt

vector<long long> tower_events(
    vector<int> H,
    vector<vector<int>> E
);

E[i] mô tả sự kiện thứ \(i\) theo quy ước trên. Hàm phải trả về mảng \(X\) độ dài \(K\), trong đó \(X[i]\) là kết quả lần đo thứ \(i\). Hàm được gọi đúng một lần và chương trình nộp không được thực hiện thao tác vào/ra.

Ràng buộc

• \(5\le N\le 1\,000\,000\).
• \(1\le Q\le 250\,000\).
• \(1\le H[i]\le 10^9\).
• Sự kiện quan sát có \(0\le I\le N-2\).
• Sự kiện đo đạc và biến động có \(0\le L\le R\le N-1\).
• Sự kiện biến động có \(-10^9\le V\le 10^9\).
• Sau mỗi biến động, mọi chiều cao vẫn không nhỏ hơn \(1\).
• Có ít nhất một sự kiện đo đạc.

Phân nhóm

Grader mẫu

Grader mẫu đọc N Q, mảng \(H\), rồi \(Q\) dòng. Mỗi dòng bắt đầu bằng độ dài \(|E[i]|\), tiếp theo là các phần tử của sự kiện. Mỗi kết quả đo được in trên một dòng.

5 5
1 2 3 4 5
1 0
2 1 3
3 1 2 1
1 1
2 0 4

3
6

10 11
7 7 9 5 8 10 2 9 2 2
1 1
3 6 8 6
1 1
2 1 9
1 3
1 8
2 2 4
1 5
3 1 1 7
1 1
2 0 9

5
3
10

Nguồn: Kỳ thi tuyển chọn đội tuyển IOI Hàn Quốc 2026 - Vòng 2, giấy phép CC BY-NC-SA 4.0.