trang chủ / đề bài / icpc24_mt_h

Cuộc thi vẽ

Đề bài

Mô tả

Bạn đang tham gia một cuộc thi vẽ. Đề thi là vẽ một đường kẻ và điều khiển độ đậm (nét) của nó.

Đề thi được mô tả bằng một mảng a gồm n số nguyên, trong đó ai (1≤i≤n) là nét mong muốn tại vị trí thứ i. Thí sinh vẽ từ trái sang phải theo các số này và điều khiển nét vẽ. Ví dụ, với a=[1,3,2,1,4,2,3,1,2,3] (n=10), đường kẻ mong muốn là cột thứ i cao đúng ai ô.

Tuy nhiên, cây cọ rất khó điều khiển: một khi đã tăng nét, bạn không thể giảm nét xuống cho đến khi rửa cọ. Vì vậy, nét thực tế tại một vị trí bằng giá trị lớn nhất của các nét mong muốn từ lúc bắt đầu vẽ (hoặc từ lần rửa cọ gần nhất) đến vị trí đó. Mỗi ô vẽ thừa so với mong muốn là một ô sai (ô X). Với ví dụ trên, nét thực tế là 1,3,3,3,4,4,4,4,4,4, tức là số ô sai lần lượt ở các vị trí là 0,0,1,2,0,2,1,3,2,1.

Trong cuộc thi có một số thời điểm thí sinh phải rửa cọ, gọi là các điểm rửa cọ. Sau khi rửa cọ tại vị trí p, nét vẽ được đặt lại ngay sau vị trí đó: từ vị trí p+1, thí sinh bắt đầu vẽ lại với nét mong muốn. Ví dụ, nếu rửa cọ tại vị trí thứ 3 và thứ 8, nét thực tế là 1,3,3∣1,4,4,4,4∣2,3.

Một bài con a[l,r] là đoạn liên tiếp al,al+1,…,ar của đề thi gốc (coi như đề thi chỉ gồm đoạn này cùng các điểm rửa cọ nằm trong nó tại thời điểm đó, các phần còn lại của đề gốc bị bỏ qua; nói riêng, việc vẽ bắt đầu tại vị trí l).

Điểm của bài con P(a[l,r]) là số ô sai (số ô X) của bức vẽ.

Ví dụ, nếu không có điểm rửa cọ nào: P(a[1,n])=1+2+2+1+3+2+1=12. Nếu có hai điểm rửa cọ tại vị trí thứ 3 và thứ 8: P(a[1,n])=1+2+1+3=7. Cũng với hai điểm rửa cọ này, P(a[6,9])=2 (nét thực tế 2,3,3,2) và P(a[8,10])=0.

Đề gốc quá dài và nhàm chán, nên ban tổ chức quyết định đưa ra lần lượt các yêu cầu sau (thay vì bắt hoàn thành cả đề gốc):

  • Yêu cầu 1: thay đổi nét mong muốn tại một vị trí. Cho hai số p và x, gán ap=x. Thay đổi này được giữ lại.
  • Yêu cầu 2: thêm một điểm rửa cọ mới tại vị trí p. Đảm bảo vị trí p chưa phải là điểm rửa cọ. Thay đổi này được giữ lại.
  • Yêu cầu 3: yêu cầu thí sinh hoàn thành bài con a[l,r].

Cho đề gốc và các yêu cầu, với mỗi yêu cầu loại 3 hãy in ra điểm P(a[l,r]) của bài con đó.

Dữ liệu vào

  • Dòng đầu tiên chứa hai số nguyên n và q (1≤n,q≤2·105): độ dài đề gốc và số yêu cầu.
  • Dòng thứ hai chứa n số nguyên a1,a2,…,an (1≤ai≤15): đề gốc.
  • q dòng tiếp theo, mỗi dòng mô tả một yêu cầu theo một trong các dạng:
    • 1 p x: gán nét mong muốn tại vị trí p bằng x (1≤p≤n, 1≤x≤15).
    • 2 p: thêm điểm rửa cọ tại vị trí p (1≤p≤n). Đảm bảo vị trí p chưa phải là điểm rửa cọ, tức là không có hai yêu cầu loại 2 nào có cùng p.
    • 3 l r: tính và in ra P(a[l,r]) (1≤l≤r≤n).

Dữ liệu ra

Với mỗi yêu cầu loại 3, in ra đáp án trên một dòng.

Ràng buộc

  • 1≤n,q≤2·105
  • 1≤ai,x≤15
  • 1≤p≤n, 1≤l≤r≤n
  • Không có hai yêu cầu loại 2 nào có cùng p.

Ví dụ

Input Output Giải thích
10 11
1 3 2 1 4 2 3 1 2 3
3 1 10
2 8
2 3
3 1 10
3 6 9
3 8 10
1 8 5
1 6 4
1 7 1
3 6 9
3 8 10
12
7
2
0
3
0
Bốn đáp án đầu như trong đề bài. Sau ba yêu cầu loại 1, a[6,9]=4,1,5,2 với điểm rửa cọ tại vị trí 8: nét thực tế 4,4,5,2, có 3 ô sai. a[8,10]=5,2,3: nét đặt lại sau vị trí 8 nên không có ô sai.
8 6
1 2 4 1 6 2 4 3
3 2 4
2 6
3 1 8
1 4 3
1 5 1
3 3 5
3
8
4
a[2,4]=2,4,1: nét 2,4,4, có 3 ô sai. a[1,8] với điểm rửa cọ tại 6: nét 1,2,4,4,6,6∣4,4, có 3+4+1=8 ô sai. Cuối cùng a[3,5]=4,3,1: có 1+3=4 ô sai.

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