CP GBUP
Xem dạng PDFNhư các bạn đã biết, VNOI là 1 câu lạc bộ chuyên về Lập trình Thi đấu (Competitive Programming - CP). Vào năm 2050, khi Trí tuệ nhân tạo đã trở thành 1 phần trong đời sống thường ngày, một nhánh mới của CP chính là CP GBUP (Generating Box Units Programming) đã trở thành 1 trào lưu, thu hút các bạn trẻ khắp thế giới.
Quỳnh Anh và Khải Duy là 2 tuyển thủ top đầu thế giới ở bộ môn CP GBUP. Sau khi bị tổ chức 83.798u - liên đoàn thế giới ở bộ môn này - cấm thi đấu vĩnh viễn ở các giải đấu quốc tế vì quá out trình, hai bạn trẻ đã trở thành tình nguyện viên VNOI nhằm đóng góp cho cộng đồng lập trình thi đấu nước nhà. Đồng thời, 2 bạn cũng đã trở thành huấn luyện viên trưởng của đội tuyển Việt Nam tham dự CGS (CP-GPUB Global Series). Và để tập huấn đội tuyển, việc chuẩn bị cho nội dung thi đấu là vô cùng quan trọng.
Nhằm giúp các thành viên đội tuyển làm quen với những bài toán đặc trưng của CP GBUP, Quỳnh Anh và Khải Duy đã xây dựng một hệ thống mô phỏng bài thi đấu. Hệ thống gồm ~n~ hộp GBUP, được đánh số từ ~1~ đến ~n~. Mỗi hộp chứa một số xâu ma thuật và có thể thay đổi nội dung trong suốt quá trình tập luyện.
Một xâu ma thuật là một xâu mà tất cả các ký tự trong xâu chỉ gồm các kí tự trong bảng chữ cái tiếng Anh thường, tức là a, b, c, …, z
Ban đầu, hộp GBUP thứ ~i~ chứa ~n_i~ xâu ma thuật
Trong quá trình tập huấn, hệ thống sẽ nhận được ~q~ truy vấn thuộc một trong bốn loại sau:
- ~1~ ~i~ ~s~: Thêm xâu ~s~ vào hộp GBUP thứ ~i~.
- ~2~ ~i~ ~s~: Xóa một lần xuất hiện của xâu ~s~ khỏi hộp GBUP thứ ~i~. Dữ liệu đảm bảo xâu ~s~ hiện đang xuất hiện trong hộp ~i~.
- ~3~ ~i~ ~j~: Lấy toàn bộ các xâu trong hộp thứ ~i~ và cho vào hộp thứ ~j~. Sau truy vấn này, hộp thứ ~i~ vẫn tồn tại, nhưng không chứa xâu nào (hộp thứ ~i~ vẫn có thể được thêm xâu trong tương lai).
- ~4~ ~i~: Các vận động viên cần phải giải quyết bài toán sau:
Xét tất cả các xâu hiện có trong hộp GBUP thứ ~i.~ Sau khi sắp xếp các xâu theo thứ tự từ điển, ta thu được ~s_1,s_2,\ldots,s_k~, với k là số xâu trong hộp thứ ~k~.
Một cách chia hợp lệ là chọn một vị trí ~j~ thỏa mãn ~1 \le j \lt k~, sau đó chia dãy trên thành hai đoạn liên tiếp: ~s_1,s_2,\ldots,s_j~ và ~s_{j+1},s_{j+2},\ldots,s_k~.
Gọi ~L_c~ là số lần xuất hiện của kí tự ~c~ ở nửa trái, và ~R_c~ là số lần xuất hiện kí tự ~c~ ở nửa phải.
Độ cân bằng của một cách chia được định nghĩa là ~\left(\sum_{c} (ord(c)+1000)L_c\right) \left(\sum_{c} (ord(c)+1000)R_c\right)~.
Cần tìm độ cân bằng lớn nhất trong tất cả các cách chia hợp lệ cho bài toán này.
Lưu ý: ~ord(c)~ là số thứ tự của ~c~ trên bảng chữ cái. Ví dụ như ~ord(~a~) = 1~, ~ord(~z~) = 26~).
Bài toán này chắc chắn là quá dễ so với Quỳnh Anh và Khải Duy, tuy nhiên lại hơi khó với các vận động viên của chúng ta. Hãy giúp các bạn trong đội tuyển giải quyết bài toán này nhé!
Input
Dòng đầu tiên chứa hai số nguyên ~n~ và ~q~ thỏa mãn ~1\le n\le 5\cdot 10^4. 1 \le q \le 10^5~.
Dòng thứ ~i~ trong ~n~ dòng tiếp theo mô tả hộp GBUP thứ ~i~. Mỗi dòng trong ~n~ dòng này bắt đầu bằng một số nguyên ~n_i~, theo sau là ~n_i~ xâu ma thuật mô tả các xâu ban đầu trong hộp.
Dữ liệu đảm bảo rằng tổng độ dài xâu trong các tập hợp (tính cả các xâu ban đầu và các xâu được thêm vào) là không quá ~2 \cdot 10^5~
Sau đó là ~q~ dòng, mỗi dòng mô tả một truy vấn thuộc một trong ba loại đã nêu:
- Đối với mỗi truy vấn loại 1 và loại 2, xâu ~s~ có độ dài từ 1 đến 12 và chỉ chứa các ký tự từ a đến z.
- Đối với truy vấn loại 2, dữ liệu đảm bảo xâu s hiện đang xuất hiện trong hộp GBUP thứ ~i~.
- Đối với mỗi truy vấn loại 3, dữ liệu đảm bảo ~i \neq j~.
- Đối với mọi truy vấn loại 4, dữ liệu đảm bảo hộp ~i~ có ít nhất 2 phần tử.
Output
Với mỗi truy vấn loại 4, in ra một dòng chứa độ cân bằng lớn nhất có thể đạt được.
Scoring
| Subtask | Điểm | Giới hạn |
|---|---|---|
| 1 | ~15~ | ~n, q \le 100~ |
| 2 | ~15~ | ~n = 1~, chỉ có truy vấn loại ~4~ |
| 3 | ~20~ | ~n = 1~, không có truy vấn loại ~3~. Mỗi xâu được thêm vào không nhỏ hơn mọi xâu trong hộp theo thứ tự từ điển. Mỗi xâu bị xóa là xâu lớn nhất trong hộp |
| 4 | ~20~ | ~n = 1~, không có truy vấn loại ~3~ |
| 5 | ~30~ | Không có ràng buộc gì thêm |
Sample Input 1
2 6
2 adq vnq
0
1 2 dnpk
4 1
3 1 2
4 2
2 2 vnq
4 2
Sample Output 1
9226166
21575551
12223990
Notes
Truy vấn 2: Hộp 1 chứa hai xâu adq, vnq. Chỉ có một cách chia, cho độ cân bằng là ~3022 \times 3053 = 9226166~.
Truy vấn 4: Sau khi chuyển xâu từ hộp 1 sang hộp 2, các xâu được sắp xếp là adq, dnpk, vnq. Chia sau xâu dnpk cho độ cân bằng lớn nhất: ~(3022+4045)\times3053=21575551~.
Truy vấn 6: Sau khi xóa vnq, hộp 2 còn adq, dnpk. Độ cân bằng là ~3022\times4045=12223990~.