trang chủ / đề bài / th_tst_26_c

Đê chắn lũ

Đề bài

Mô tả

Dọc theo một con sông có n đoạn đê liên tiếp, đoạn thứ i có chiều cao ban đầu là ai. Một đoạn đê được gọi là an toàn nếu chiều cao của nó không nhỏ hơn ngưỡng C. Trong mùa mưa, trung tâm điều hành phải xử lý Q yêu cầu thuộc một trong bốn loại sau:

  • Loại 1: cho ba số l,r,h, yêu cầu hạ toàn bộ các đoạn đê trong đoạn [l,r] xuống không vượt quá h, tức gán ai=min(ai,h) với mọi l≤i≤r.
  • Loại 2: cho hai số l,r, yêu cầu tính tổng chiều cao của các đoạn đê từ l đến r.
  • Loại 3: cho hai số l,r, yêu cầu tìm chiều cao lớn nhất của một đoạn đê trong đoạn [l,r].
  • Loại 4: cho hai số l,r, yêu cầu đếm số cụm an toàn trong đoạn [l,r]. Một cụm an toàn là một đoạn con liên tiếp cực đại (trong [l,r]) chỉ gồm các đoạn đê an toàn.

Yêu cầu: Hãy trả lời mọi truy vấn loại 2, loại 3 và loại 4.

Dữ liệu vào

  • Dòng đầu chứa ba số nguyên n,Q,C (1≤n,Q≤200000, 0≤C≤109).
  • Dòng tiếp theo chứa n số nguyên dương a1,a2,…,an (1≤ai≤109).
  • Q dòng tiếp theo mô tả các truy vấn. Với truy vấn loại 1, ta có 1 l r h (1≤l≤r≤n, 0≤h≤109). Với truy vấn loại 2, 3 hoặc 4, ta có t l r với t∈{2,3,4} và 1≤l≤r≤n.

Dữ liệu ra

Với mỗi truy vấn loại 2, loại 3 và loại 4, ghi ra trên một dòng kết quả tương ứng.

Ràng buộc

  • 1≤n,Q≤200000, 0≤C≤109
  • 1≤ai≤109, 0≤h≤109

Subtasks

  • Subtask 1 (10% số điểm): n,Q≤2000.
  • Subtask 2 (15% số điểm): không có truy vấn loại 1.
  • Subtask 3 (20% số điểm): mọi truy vấn loại 1 đều có l=1 và r=n.
  • Subtask 4 (20% số điểm): n,Q≤50000.
  • Subtask 5 (35% số điểm): không có ràng buộc gì thêm.

Ví dụ

Input Output Giải thích
6 8 5
7 2 6 5 9 3
4 1 6
1 2 5 6
2 1 6
1 1 4 4
4 1 6
3 1 6
1 5 5 1
4 1 6
2
29
1
6
0
Ban đầu các đoạn an toàn là 1,3,4,5, nên trong đoạn [1,6] có hai cụm an toàn: [1,1] và [3,5]. Sau khi hạ đoạn [2,5] xuống không vượt quá 6, dãy trở thành 7,2,6,5,6,3 nên tổng là 29. Hạ đoạn [1,4] xuống không vượt quá 4, chỉ còn vị trí 5 an toàn: có 1 cụm, chiều cao lớn nhất là 6. Cuối cùng hạ vị trí 5 xuống 1 thì không còn cụm an toàn nào.
5 7 3
3 4 1 3 5
4 2 5
1 1 5 3
2 1 5
4 1 5
1 4 4 2
4 1 5
3 2 4
2
13
2
2
3
Ví dụ thêm (không có trong đề gốc). Đoạn đê có chiều cao đúng bằng C=3 vẫn an toàn. Trong [2,5] có hai cụm [2,2] và [4,5]. Sau khi hạ cả dãy xuống không vượt quá 3, dãy là 3,3,1,3,3 với tổng 13 và hai cụm. Hạ vị trí 4 xuống 2: còn hai cụm [1,2] và [5,5]; chiều cao lớn nhất trong [2,4] là 3.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0