Sequence queries

Xem dạng PDF
Gửi bài giải
Điểm: 1,80 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 512M
Input: stdin
Output: stdout
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Cho một dãy số và các loại truy vấn sau:

  • 1 ~A~ ~B~ ~X~: gán các phần từ thứ ~A~ đến thứ ~B~ trong dãy bằng ~X~.
  • 2 ~A~ ~B~ ~X~: cộng phần tử thứ ~A~ cho ~X~, thứ ~A~ + 1 cho ~2X~,..., thứ ~B~ cho ~(B - A + 1) \times X~.
  • 3 ~C~ ~X~: chèn ~X~ vào trước phần tử thứ ~C~ của dãy hiện thời.
  • 4 ~A~ ~B~: tính tổng từ phần tử thứ ~A~ đến thứ ~B~.

Input

  • Dòng đầu ghi hai số nguyên ~N~ và ~Q~, số phần tử của dãy ban đầu và số truy vấn ~(1 \leq N, Q \leq 10^5)~.
  • Dòng tiếp theo mô tả dãy số. Mỗi số không vượt quá ~10^5~.
  • ~Q~ dòng tiếp theo mô tả các truy vấn theo định dạng như trong đề bài. Trong mọi truy vấn, ~0 \leq X \leq 100~, ~1 \leq A \leq B \leq~ độ dài dãy hiện thời, ~1 \leq C \leq~ (độ dãy dãy hiện thời + 1).

Output

  • In ra trên từng dòng câu trả lời cho mỗi truy vấn loại 4.

Sample Input 1

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

Sample Output 1

4
0
25

Sample Input 2

1 7 
100 
3 1 17 
3 2 27 
3 4 37 
4 1 1 
4 2 2 
4 3 3 
4 4 4

Sample Output 2

17
27
100
37

Bình luận

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


  • -2
    pt48583994  đã bình luận lúc 27, Tháng 7, 2025, 14:45

    Cách làm của mình:

    Có thể mở rộng các thao tác trên thành ~A_i=k * A_i + c~ và ~A_i=A_i + k * i + c~. 2 thao tác này có thể gộp thành 1 thao tác chung làm cả 2. Sau đó dùng BBST hoặc chia căn lazy.


  • 3
    pppssslc  đã bình luận lúc 15, Tháng 7, 2025, 9:24 ← sửa 2

    My solve:

    Chia căn:

    • Ta có các mảng:
    • ~updx~: lazy cho truy vấn loại 1 của mỗi block.
    • ~lazy~: lazy cho truy vấn loại 2 của mỗi block.
    • ~st, en~: vị trí bắt bầu và kết thúc của mỗi block.
    • Đối với truy vấn loại 1:
    • Đối với phần lẻ ra ở 2 đầu:
    • Cập nhật block chứa lẻ ra đó.
    • Sau đó, ta sẽ cập nhật phần lẻ ra đó.
    • Đối với các block nằm hoàn toàn trong đoạn ~[l, r]~:
    • Ta sẽ xóa hết ~lazy~ của block đó.
    • Cập nhật ~udpx~ của block đó.
    • Đối với truy vấn loại 2:
    • Đối với phần lẻ ra ở 2 đầu:
    • Cập nhật block chứa phần lẻ ra.
    • Sau đó, ta sẽ cập nhật phần lẻ ra đó.
    • Đối với các block nằm hoàn toàn trong đoạn ~[l, r]~:
    • Cập nhật ~lazy~ của block đó.
    • Đối với truy vấn loại 3:
    • Cập nhật block có chứa ~c~.
    • Sau đó ta sẽ chèn ~x~ vào vị trí tương ứng trong block đó.
    • Sau đó ta sẽ cập nhật mảng ~st~ và ~en~.
    • Đối với truy vấn loại 4:
    • Cập nhật block chứa phần lẻ ra sau đó tính tổng phần lẻ ra.
    • Tính tổng các block nằm hoàn toàn trong đoạn ~[l, r]~.
    • Sau nhiều truy vấn, chênh lệch giữa các block quá lớn:
    • Ta sẽ build lại các block.

    ĐPT: ~O(n\sqrt{n})~

    Tuy nhiên, bài này test rất yếu, code có đpt ~O(n^2)~ và thêm pragma cũng có thể AC.


  • 4
    KAKOII  đã bình luận lúc 8, Tháng 7, 2025, 6:51

    Gợi ý giải:

    Ta có thể giải bài toán này bằng phương pháp chia căn, với ý tưởng gần như tương tự với bài Reversals and Sums