Tách từ

Xem dạng PDF

Gửi bài giải


Điểm: 0,68 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 512M
Input: stdin
Output: stdout

Nguồn bài:
Ðinh Ngọc Thắng
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Một từ trong tiếng Việt được cấu tạo nên từ các âm tiết. Khi cho một câu trong tiếng Việt, việc tách các âm tiết thành các từ riêng biệt là một công việc cần thiết nhưng không đơn giản. Chẳng hạn câu: "Ông già đi nhanh quá" có thể được tách thành "/Ông/ già đi /nhanh / quá/" hoặc "Ông già/ đi / nhanh /quá". Bạn là trợ lý của giáo sư có danh tiếng, công việc của bạn là giúp giáo sư viết một chương trình tách từ. Phần cốt lõi của chương trình là việc mô tả một cấu trúc dữ liệu cho phép thực hiện ba thao tác cơ bản trên ~1~ dãy ~n~ đơn âm cho trước (các đơn âm được đánh số lần lượt từ ~1~ tới ~n~, theo thứ tự từ trái qua phải). Hai đơn âm cạnh nhau có thể được nối, hoặc không nối với nhau, một từ là một dãy đơn âm liên tiếp (cực đại) nối với nhau. Các thao tác trên cấu trúc dữ liệu bao gồm:

  • ~J~ ~i~ ~j~: Nối từ đơn âm thứ ~i~ tới đơn âm thứ ~j~ với nhau
  • ~D~ ~i~ ~j~: Tách các đơn âm từ đơn âm thứ ~i~ tới đơn âm thứ ~j~ (~i~ ~\leq~ ~j~)
  • ~C~: Đòi hỏi trả về số lượng từ (số lượng dãy đơn âm nối nhau)

Chẳng hạn với ~n~ = ~4~ và trạng thái hiện tại của dãy đơn âm đang là (1_2 3_4):

  • ~J~ ~2~ ~3~: Dãy đơn âm sẽ biến đổi thành: 1_2_3_4
  • ~D~ ~2~ ~4~: Dãy đơn âm sẽ biến đổi thành: 1_2 3 4
  • ~C~: Trả về giá trị: ~3~, do có ba từ là 1_2, 3 và 4

Input

  • Dòng đầu ghi số ~K~ là số từ trong dãy ban đầu và số ~M~ là số lượng thao tác.
  • Dòng tiếp theo ghi ~K~ số nguyên dương lần lượt là độ dài của các từ tính từ trái qua phải
  • ~M~ dòng tiếp theo mỗi dòng bắt đầu bằng ~1~ chữ cái (J/D/C). Trong trường hợp chữ cái bắt đầu là ~J~ hoặc ~D~ tiếp theo ghi số hiệu từ mà thao tác cần thực hiện.

Output

  • Ứng với mỗi thao tác ~C~ trong input, ghi ra ~1~ số trên ~1~ dòng trong file output là số lượng từ tại thời điểm tương ứng.
  • Giới hạn: Số đơn âm không quá ~50000~. ~M~ ~\leq~ ~100000~

Sample Input

2 3
2 2
J 2 3
D 2 4
C

Sample Output

3

Bình luận

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



  • 6
    CQTshadow  đã bình luận lúc 19, Tháng 5, 2021, 9:19 chỉnh sửa

    +) Đừng nhìn mấy phần tử đơn âm nữa, nhìn khoảng liên kết giữa chúng ấy

    +) Nếu chúng ta có số lượng các liên kết thì kết quả sẽ là gì ?

    [Tổng các đơn âm (tổng K phần tử ban đầu) ] - [ số lượng liên kết]


  • 2
    CQTshadow  đã bình luận lúc 19, Tháng 5, 2021, 7:52 sửa 3

    [ deleted ]


    • 2
      leduykhongngu  đã bình luận lúc 19, Tháng 5, 2021, 8:11

      Mình vừa cập nhật lại đề bài rồi nhé :3