trang chủ / đề bài / icpc25_nat_g

Làm đẹp xâu

Đề bài

Mô tả

FWMC nhận được một xâu s độ dài n, gồm các ký tự s0,s1,…,sn−1, làm quà sinh nhật. Ban đầu, mọi ký tự trong s đều là chữ cái A.

Sau đó FWMC bắt đầu nghịch xâu này. Quá trình được mô tả bằng một dãy q truy vấn, mỗi truy vấn thuộc một trong hai loại sau:

  • 1 l r c: FWMC gán ký tự c cho mọi vị trí i trong đoạn [l,r] (tức là đặt si=c với mọi l≤i≤r).
  • 2 k: FWMC không thích những dãy dài các ký tự giống nhau liên tiếp. FWMC coi một xâu là tốt nếu không có xâu con liên tiếp nào gồm nhiều hơn k ký tự giống nhau. Với xâu s hiện tại, FWMC muốn biết số ký tự ít nhất cần xóa để s trở thành xâu tốt.

    Lưu ý rằng FWMC chỉ muốn biết số ký tự ít nhất cần xóa, chứ không thực sự thay đổi s.

Nhiệm vụ của bạn là giúp FWMC trả lời mọi truy vấn loại thứ hai.

Một xâu α là xâu con liên tiếp của xâu β nếu α nhận được từ β bằng cách xóa một số (có thể là không hoặc tất cả) ký tự ở đầu và một số (có thể là không hoặc tất cả) ký tự ở cuối.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên n và q (1≤n,q≤300000): độ dài xâu và số truy vấn.

Mỗi dòng trong q dòng tiếp theo mô tả một truy vấn. Số nguyên đầu tiên là t (1≤t≤2): loại truy vấn.

  • Nếu t=1: tiếp theo là hai số nguyên l và r (0≤l≤r<n) và một chữ cái Latin in hoa c.
  • Nếu t=2: tiếp theo là một số nguyên k (1≤k≤n).

Dữ liệu ra

Với mỗi truy vấn loại thứ hai, in ra một số nguyên: số ký tự ít nhất cần xóa để xâu trở thành xâu tốt.

Ràng buộc

  • 1≤n,q≤300000.
  • 0≤l≤r<n, c là chữ cái Latin in hoa.
  • 1≤k≤n.

Ví dụ

Input Output Giải thích
11 10
1 0 1 F
1 2 10 C
1 3 8 W
1 9 9 M
1 4 6 M
2 2
2 1
2 5
1 5 7 C
2 1
1
4
0
3
Năm truy vấn đầu biến đổi xâu: AAAAAAAAAAA → FFAAAAAAAAA → FFCCCCCCCCC → FFCWWWWWWCC → FFCWWWWWWMC → FFCWMMMWWMC. Truy vấn 6 (k=2): xóa một ký tự được FFCWMMWWMC, các nhóm FF, C, W, MM, WW, M, C đều không quá 2 ký tự. Truy vấn 7 (k=1): xóa 4 ký tự, ví dụ được FCWMWMC, không thể xóa ít hơn. Truy vấn 8 (k=5): xâu đã tốt. Truy vấn 9 biến xâu thành FFCWMCCCWMC; truy vấn 10 (k=1): xóa 3 ký tự, ví dụ được FCWMCWMC.
12 5
1 3 7 G
1 7 11 G
1 4 5 C
1 0 6 C
2 2
8 Xâu cuối cùng là CCCCCCCGGGGG: nhóm 7 chữ C và nhóm 5 chữ G, cần xóa 5+3=8 ký tự.

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