# Đề DeMen #9 (Mock dự tuyển 10 #2) > Tác giả `Minhho2005`, `Megumin`, `Chris`. # Bài 1: SANDWICH.* Đầu bếp sẽ tham gia chương trình thực tế 'Ai sẽ chuẩn bị bánh mì đẹp nhất?'. Chương trình yêu cầu người tham gia chuẩn bị những chiếc bánh mì không chỉ đẹp mắt mà còn có hương vị thơm ngon. Chương trình cũng công bố danh sách các thành phần mà bạn được phép sử dụng trong bánh sandwich. Lần này, danh sách bao gồm $K$ thành phần. Đối với mục đích của vấn đề của chúng tôi, bạn có thể giả sử rằng mỗi thành phần được biểu thị bằng một ký tự Latin viết thường. Vì vậy, chữ cái Latinh viết thường K đầu tiên sẽ mô tả tất cả các thành phần. Bánh sandwich của đầu bếp bao gồm $N$ phần nguyên liệu xếp thành một hàng ngang. Có thể coi nó như một chuỗi có độ dài $N$ chỉ chứa $K$ chữ cái tiếng Anh đầu tiên. Đầu bếp cho rằng vẻ đẹp của chiếc bánh sandwich là một số nguyên có thể được tính theo cách sau: - Đầu tiên chia bánh sandwich thành các đoạn con liên tiếp sao cho tất cả các phần trong cùng một khối đều có cùng thành phần và không có hai đoạn con nào đứng cạnh nhau và có cùng thành phần. - Vẻ đẹp của chiếc bánh sandwich này là tổng bình phương độ dài của các đoạn con. **Ví dụ**: bánh sandwich được ký hiệu là $aadddbabb$. - Đầu bếp chia thành các đoạn con $-$ $aa$, $ddd$, $b$, $a$, $bb$. - Vẻ đẹp của chiếc bánh sandwich này bằng $2*2 + 3*3 + 1*1 + 1*1 + 2*2 = 19$. Đầu bếp có thể cắt một thành phần phía bên trái và đưa về bên phải sandwich của mình và có thể thực hiện vô số lần cắt như vậy. **Ví dụ**: đầu bếp có thể thực hiện hành động cắt sandwich $aadddbabb$ thành một sandwich khác là $adddbabba$. Với vai trò là trợ lý toàn năng của đầu bếp, bạn có nhiệm vụ tìm xem vẻ đẹp lớn nhất mà đầu bếp có thể đạt được. **Yêu cầu:** Tính độ đẹp lớn nhất của chiếc bánh mà đầu bếp có thể đạt được. ### Input - Dòng đầu tiên chứa một số nguyên $N$ và $K$ được phân tách bằng dấu cách, lần lượt biểu thị số lượng phần trong bánh sandwich và số lượng nguyên liệu sẵn có. - Dòng thứ hai chứa một xâu có độ dài $N$ chỉ có ký tự chữ thường $K$ Latinh đầu tiên, biểu thị bánh sandwich. ### Output - Một dòng duy nhất là vẻ đẹp lớn nhất mà đầu bếp đạt được. ## Sample Input 7 4 acabada ## Sample Output 9 ### Giới hạn - $50$% số test có $N ≤ 5000, K <= 26$. - $50$% số test còn lại có $N ≤ 10^6, K <= 26$. # Bài 2: KONGROO.* Tại chiều không gian Delta, tuy không cứu được Kurisu nhưng chiến tranh thế giới thứ 3 đã không xảy ra và Mayuri vẫn được sống. Quyết tâm bảo vệ sự bình yên của mọi người, Okabe phá hủy toàn bộ cỗ máy thời gian và quay lại cuộc sống của một người bình thường. Một lần vô tình, cậu tìm ra được một vấn đề mà Kurisu còn đang giải quyết dang dở và quyết tâm hoàn thành nó giúp cô, vấn đề ấy như sau: Cho một dãy $a$ gồm $n$ phần tử và các truy vấn. Mỗi truy vấn thuộc 1 trong 2 dạng: 1. Dịch chuyển "tuần hoàn" đoạn $[l, r]$ như sau: $a_l, a_{l+1}, ..., a_{r-1}, a_r$ &nbsp;&rarr;&nbsp; $a_r, a_l, a_{l+1}, ..., a_{r - 1}$. 2. Đếm số lượng số bằng $k$ trong đoạn $[l, r]$ của dãy $a$. ### Input - Dòng đầu chứa số nguyên $n$ - số lượng phần tử của dãy. - Dòng thứ 2 chứa n số nguyên $a_1, a_2, ..., a_n$ là các phần tử của dãy ($a_i ≤ 2 * 10^5$). - Dòng thứ 3 chứa số nguyên $q$ - số lượng truy vấn. - $q$ dòng tiếp theo, mỗi dòng là một truy vấn: -- Truy vấn loại $1$ có dạng $1$ $l$ $r$: dịch chuyển tuần hoàn đoạn $[l, r]$. -- Truy vấn loại $2$ có dạng $2$ $l$ $r$ $k$: đếm số lượng số bằng $k$ trong đoạn $[l, r]$. ### Output - Với mỗi truy vấn loại $2$, in ra kết quả trên 1 dòng. ## Sample Input 10 4 2 1 5 3 4 4 3 2 4 10 2 2 9 4 2 1 7 5 1 2 10 1 5 8 2 2 9 4 2 3 10 5 1 7 10 2 9 10 5 1 6 7 1 4 7 ## Sample Output 2 1 3 1 0 ### Giới hạn - $50$% số test ứng với $n, q ≤ 10^3$. - $50$% số test còn lại ứng với $n, q ≤ 2*10^5$. # Bài 3: XORSEG.* Cho dãy số $a_1,a_2,…,a_n$. Có 2 truy vấn: 1. $i$ $x$: gán $a_i=x$ $(x,a_i≤10^8)$. 2. $u$ $v$: tính tổng các giá trị là tổng xor của tất cả các đoạn $[l,r]$ có $u≤l≤r≤v$. ### Input - Dòng đầu chứa 2 số nguyên $n,m$. - Dòng thứ hai chứa n số nguyên $a_1,a_2,…,a_n$. - $m$ dòng cuối, mỗi dòng chứa thông tin thuộc một trong $2$ loại truy vấn theo thứ tự. ### Output - Với mỗi truy vấn loại $2$, đưa ra đáp số trên một dòng. ## Sample Input 3 3 1 1 1 2 1 3 1 2 2 2 1 3 ## Sample Output 4 12 ## Giới hạn - $10$% số test có $n, m ≤ 300$ - $15$% số test chỉ có truy vấn thuộc loại 2 và $n ≤ 3000$, $m ≤ 10^5$ - $25$% số test có $n, m ≤ 3000$ - $50$% số test có $n, m ≤ 10^5$ # Bài 4: MEETING.* Chính phủ Siruseri xây dựng một trung tâm hội nghị quốc gia mới. Một số công ty đã đến đăng ký thuê để tổ chức các cuộc hội nghị của mình. Các công ty yêu cầu phải được sử dụng trung tâm liên tục trong khoảng thời gian mà mình đăng ký. Trưởng phòng tiếp thị của trung tâm có quan điểm cho rằng, cách tiếp thị tốt nhất là đảm bảo được càng nhiều công ty được thuê càng tốt. Rõ ràng là có nhiều cách thực hiện được điều này. ![](https://i.imgur.com/YoVTHfK.png) Ví dụ, có $4$ công ty đăng ký thuê, đánh số từ 1 đến 4 theo trình tự đăng ký và danh sách thời hạn sử dụng là như sau: Rõ ràng là chỉ có thể đáp ứng được yêu cầu của 2 công ty: 1 và $3$ hoặc $1$ và $4$ hoặc $2$ và $3$. Yêu cầu của các công ty $1$ và $2$ không thể đồng thời đáp ứng vì bị trùng nhau ngày $9$. Là một người chính trực, trưởng phòng tiếp thị quyết định đưa ra quy trình chọn như sau: Liệt kê các phương án đáp ứng yêu cầu, mỗi phương án là danh sách các công ty có yêu cầu đáp ứng được và chọn danh sách dài nhất (chứa nhiều công ty nhất). Trong mỗi danh sách các công ty được sắp xếp theo thứ tự tăng dần, tức là theo trình tự đăng ký. Nếu có nhiều danh sách cùng là dài nhất thì chọn danh sách có thứ tự từ điển nhỏ nhất. Ở ví dụ trên, ta có các phương án ${(1, 3), (1, 4), (2, 3)}$ và vì $(1,3) < (1, 4) < (2, 3)$ nên hai công ty $1$ và $3$ sẽ được thuê. ### Yêu cầu ### Cho $n$ – số lượng công ty đăng ký thuê, các ngày đầu và cuối trong thời hạn thuê của mỗi công ty ($1≤n≤200000$, ngày đầu và cuối – nguyên dương, không vượt quá $10^9$, ngày đầu nhỏ hơn hoặc bằng ngày cuối). Hãy xác định $m$ $-$ số công ty được thuê và đưa ra danh sách các công ty này theo thứ tự tăng dần. ## Input - Dòng đầu tiên chứa số nguyên $n$ - Dòng thứ $i$ trong $n$ dòng sau chứa $2$ số nguyên: ngày đầu và ngày cuối theo yêu cầu của công ty thứ $i$. ## Output - Dòng đầu tiên đưa ra số nguyên $m$ - Dòng thứ $2$ chứa $m$ số nguyên theo thứ tự tăng dần – danh sách các công ty được thuê. ## Sample Input 4 4 9 9 11 13 19 10 17 ## Sample Output 2 1 3 ## Giới hạn 20% số điểm có $n≤20$. 30% số điểm có $n≤300$. 50% số điểm không có giới hạn nào thêm.