Bài này em sử dụng splay tree để xử lí truy vấn 1,3,4, nhưng ko biết làm sao để xử lí được truy vấn số 2:
2 A B X: cộng phần tử thứ A cho X, thứ A + 1 cho 2X,... , thứ B cho (B - A + 1) * X.
Mong mọi người giúp đỡ cho em ý tưởng ạ :D :D
Forum VNOI đã tạm ngừng hoạt động. Các bạn có thể hỏi bài trên Group Facebook của bọn mình.
Trên Interval tree thông thường thì bạn làm đc thao tác cộng này ko? Đơn giản chỉ là lưu lại ở mỗi nút, nó được cộng thêm cấp số cộng nào bằng lazy propagation
các nút trên cây it phải lưu những thông tin j vậy a, tại trên it e ko cài dc nên trên cây splay mới ko cài dc đấy ạ :3 :3
Hình dung là mỗi nút đc cộng thêm 1 cấp số cộng.
Xét đoạn [l, r]. Giả sử nó đc cộng thêm cấp số cộng A + k*B (nghĩa là, gọi dãy số là x, thì x[l] đc cộng A, x[l+1] + A + B, x[l+2] + A + 2*B.....) --> cần lưu thêm A, B :))