trang chủ / đề bài / icpc21_nat_k

Truy vấn K

Đề bài

Mô tả

Cho một dãy các quả bóng, mỗi quả có màu đen hoặc trắng. Ban đầu dãy có n quả bóng. Bạn cần lần lượt thực hiện q truy vấn. Ở mỗi truy vấn, gọi m là số quả bóng trong dãy trước khi truy vấn diễn ra, và đánh số các quả bóng từ 1 đến m theo thứ tự từ trái sang phải. Mỗi truy vấn có một trong các dạng sau:

  • I x k c (0≤x≤m, 1≤k≤109, c là B hoặc W): chèn k quả bóng màu c vào dãy, ngay sau quả bóng thứ x. Cụ thể:
    • Nếu x=0, các quả bóng được chèn vào đầu dãy.
    • Nếu 1≤x<m, các quả bóng được chèn vào giữa quả bóng thứ x và quả bóng thứ x+1.
    • Nếu x=m, các quả bóng được chèn vào cuối dãy.
    • Nếu c là B, mọi quả bóng được chèn đều màu đen; nếu c là W, mọi quả bóng được chèn đều màu trắng.
  • D x k (1≤x≤m, 1≤k≤m−x+1): xóa k quả bóng liên tiếp khỏi dãy, bắt đầu từ quả bóng thứ x.
  • F x k (1≤x≤m, 1≤k≤m−x+1): đổi màu k quả bóng liên tiếp bắt đầu từ quả bóng thứ x. Nói cách khác, mỗi quả bóng đen được thay bằng một quả bóng trắng ở cùng vị trí, và ngược lại.
  • Q x k (1≤x≤m, 1≤k≤m−x+1): chỉ xét k quả bóng liên tiếp bắt đầu từ quả bóng thứ x, chia chúng thành ít đoạn nhất sao cho mỗi đoạn gồm các quả bóng liên tiếp cùng màu, và gọi l1,l2,…,lt là độ dài các đoạn này. Hãy tính và in ra giá trị l12+l22+…+lt2. Lưu ý rằng cách chia này luôn là duy nhất.

Dữ liệu vào

  • Dòng đầu tiên chứa hai số nguyên n và q.
  • Dòng thứ hai chứa n ký tự B hoặc W, mô tả màu của các quả bóng trong dãy ban đầu (B là đen, W là trắng).
  • q dòng tiếp theo, mỗi dòng chứa một truy vấn theo mô tả ở trên.

Dữ liệu ra

Với mỗi truy vấn dạng Q x k, in ra kết quả trên một dòng. Vì kết quả có thể rất lớn, hãy in ra phần dư khi chia cho 998244353.

Ràng buộc

  • 1≤n,q≤200000.
  • Các tham số của truy vấn thỏa mãn các ràng buộc nêu ở trên.

Ví dụ

Input Output Giải thích
8 2
WWWBBWWW
Q 1 2
Q 2 6
4
12
Dãy không đổi. Truy vấn thứ nhất xét WW, chỉ có một đoạn, kết quả là 22=4. Truy vấn thứ hai xét WWBBWW, gồm ba đoạn: 2 bóng trắng, 2 bóng đen và 2 bóng trắng, kết quả là 22+22+22=12.
5 7
BBWBB
Q 2 3
I 0 3 B
Q 3 4
F 4 3
Q 4 2
D 4 2
Q 1 6
3
10
4
36
Ban đầu dãy là BBWBB. Truy vấn thứ nhất xét BWB, gồm ba đoạn một bóng, kết quả là 3. Sau truy vấn thứ hai, dãy là BBBBBWBB. Truy vấn thứ ba xét BBBW: 32+12=10. Sau truy vấn thứ tư, dãy là BBBWWBBB. Truy vấn thứ năm xét WW: 22=4. Sau truy vấn thứ sáu, dãy là BBBBBB. Truy vấn cuối xét cả dãy: 62=36.

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