LQDOJ CUP 2023 - Round 7

Cho một xâu \(s\) độ dài \(n\) chỉ gồm các ký tự Latin in thường (từ a đến z). Có \(q\) truy vấn, mỗi truy vấn cho hai số nguyên \(l\) và \(r\), hãy đếm có bao nhiêu cặp nghịch thế trong xâu con liên tiếp từ \(l\) đến \(r\).

Số cặp nghịch thế là số cặp \(i\), \(j\) sao cho \(i < j\) và ký tự ở vị trí \(i\) nằm sau ký tự ở vị trí \(j\) trong thứ tự từ điển. Ví dụ, xâu beac có \(3\) cặp nghịch thế, đó là \((1, 3)\), \((2, 3)\) và \((2, 4)\).

Input

• Dòng đầu tiên chứa số nguyên \(n\) \((1 \leq n \leq 5 \times 10^5)\) là độ dài của xâu.
• Dòng tiếp theo chứa xâu \(s\) có độ dài \(n\) chỉ gồm các ký tự Latin in thường.
• Dòng tiếp theo chứa số nguyên \(q\) \((1 \leq q \leq 5 \times 10^5)\) là số truy vấn.
• Trong \(q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(l\) và \(r\) \((1 \leq l \leq r \leq n)\) mô tả một truy vấn.

Output

• Gồm \(q\) dòng, mỗi dòng là số cặp nghịch thế của truy vấn tương ứng.

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(n, q \leq 5 \times 10^2\).
• Subtask \(2\) (\(25\%\) số điểm): \(n, q \leq 5 \times 10^3\).
• Subtask \(3\) (\(25\%\) số điểm): \(n, q \leq 5 \times 10^4\).
• Subtask \(4\) (\(25\%\) số điểm): Không có ràng buộc gì thêm.

Example

7
adbcedc
4
1 4
3 5
4 7
2 4

2
0
3
2

Winko - vũ khí súng bắn tia plasma do công ty Q nghiên cứu chế tạo vào thế kỉ 23 có sức công phá cao, được phe Nổi loạn (Rebellion) dự kiến sử dụng trong trận chiến cuối cùng với Đế chế Thiên hà (Galactic Empire). Vũ khí gồm \(n\) thành phần bố trí trên một đường thẳng, các thành phần được tích lượng điện năng lần lượt là \(a_1, a_2, a_3, \ldots, a_n\). Điều kiện để Winko hoạt động được là điện năng của mỗi thành phần phải bé hơn mọi thành phần nằm phía sau nó, tức \(a_i < a_j\) với mọi \(1 \leq i < j \leq n\).

Tuy nhiên, trước khi kịp sử dụng, Đế chế đã âm mưu hủy hoại vũ khí này. Bằng một phát đạn pháo từ trường cực mạnh, điện năng của các thành phần của súng đã bị nhiễu loạn, và không còn kích hoạt được nữa. Phe Nổi loạn cần nhanh chóng sửa chữa vũ khí trước trận chiến quan trọng. Họ có một công cụ sửa chữa đặc biệt. Trong một giây, công cụ này có thể hoán đổi lượng điện năng nằm trong hai thành phần liền kề, sau đó đổi dấu chúng. Tức là, nếu sử dụng công cụ lên thành phần \(1 \leq i < n\), thì \(a_i \leftrightarrow a_{i + 1}\), sau đó \(a_i \leftarrow -a_i, a_{i + 1} \leftarrow -a_{i + 1}\) (Do đặt trong bối cảnh khoa học viễn tưởng, nên năng lượng có thể âm và đổi dấu).

Tuy nhiên, nếu vũ khí không thể nào phục hồi được, phe Nổi loạn sẽ tìm sách lược khác để đối phó với Đế chế. Hỏi, với tình trạng điện năng được cho bởi \(a\), thì có sửa vũ khí về trạng thái có thể kích hoạt được hay không?

Lưu ý rằng vấn đề trên được đặt ra trong \(t\) vũ trụ song song riêng biệt nhau. Trong mỗi tình huống đặt ra, cần phải giải quyết các vấn đề một cách độc lập.

Input

• Dòng đầu tiên chứa số nguyên \(t\) \((1 \le t \le 20)\) là số tình huống riêng biệt cần xử lý.
• Trong \(t\) nhóm dòng tiếp theo, mỗi nhóm có dạng sau:
  • Dòng đầu chứa số nguyên \(n\) \((1 \le n \le 10^5)\) là số thành phần của vũ khí.
  • Dòng tiếp theo chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) \((0 < |a_i| \le 10^9)\) là lượng điện năng ban đầu trong mỗi thành phần của vũ khí.

Output

• Gồm \(t\) dòng, mỗi dòng chứa YES nếu trong tình huống tương ứng, phe Nổi loạn có thể sửa được vũ khí và NO trong trường hợp còn lại.

Scoring

• Subtask \(1\) (\(32\%\) số điểm): \(n\) là số chẵn và với mọi \(i\) \((1\le i \le n)\), tồn tại \(j \neq i\) sao cho \(a_i + a_j = 0\).
• Subtask \(2\) (\(18\%\) số điểm): \(n \le 20\).
• Subtask \(3\) (\(27\%\) số điểm): \(n \le 1000\).
• Subtask \(4\) (\(23\%\) số điểm): Không có ràng buộc gì thêm.

Example

4
7
-4 2 1 -5 4 6 3
7
-7 -4 3 3 -2 8 -7
7
1 2 -4 7 -3 5 -5
7
-6 7 2 3 -3 -7 2

YES
NO
NO
NO

Vương quốc Byteland bao gồm \(n\) thành phố, các thành phố được đánh số từ \(1\) đến \(n\). Chúng được kết nối với nhau bằng \(m\) con đường hai chiều, sao cho tồn tại đường đi giữa mọi cặp hai thành phố bất kỳ.

Sắp tới là kỉ niệm 100 năm thành lập vương quốc, nhà vua muốn tổ chức lễ hội, và do đó cần chọn ra một số thành phố làm nơi tổ chức sự kiện. Vì ngân sách giới hạn, nhà vua chỉ có thể chọn không quá \(k\) thành phố. Giả sử \(k\) thành phố được chọn là \(v_1, v_2, v_3, \ldots, v_k\), thì:

• Chúng phải thỏa mãn điều kiện: Với \(i \neq j\) bất kì, đường đi từ \(v_i\) tới \(v_j\) chỉ được phép đi qua các thành phố tổ chức lễ hội.
• Vì các thành phố có chỉ số gần nhau (\(i\) và \(i+1\)) thường có mối quan hệ giao thương rất tốt, nên nhà vua đánh giá mức độ hiệu quả của lễ hội là kích thước lớn nhất có thể của bất kỳ tập con các thành phố trong \(v\) có các chỉ số nằm liên tiếp nhau (tức là chỉ số của các thành phố đó tạo thành đoạn liên tiếp \(l, l+1, l+2, \ldots, r-1, r\)).

Hãy giúp nhà vua chọn ra phương án tổ chức lễ hội có mức độ hiệu quả lớn nhất!

Input

• Dòng đầu tiên chứa ba số nguyên \(n\), \(m\) và \(k\) \((1 \le k \le n \le 3 \times 10^5, 1 \leq m < n)\) lần lượt là số thành phố, con đường và số thành phố tối đa được chọn.
• Trong \(m\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u\) và \(v\) \((1 \leq u, v \leq n)\) ứng với đường đi nối hai thành phố \(u\) và \(v\).

Output

• Gồm một số nguyên duy nhất là mức độ hiệu quả lớn nhất của một phương án.

Scoring

Gọi \(d_i\) là số con đường nối trực tiếp từ thành phố \(i\) tới các thành phố khác.

• Subtask \(1\) (\(20\%\) số điểm): \(n \le 2000\).
• Subtask \(2\) (\(30\%\) số điểm): \(d_u \le 2\) với mọi \(1 \le u \le n\).
• Subtask \(3\) (\(20\%\) số điểm): Tồn tại ít nhất một thành phố \(r\) có \(d_r \le 2\), và mọi thành phố \(u\) \((1 \le u \le n)\) đều thỏa mãn \(d_u \le 3\). Ngoài ra, độ dài đường đi ngắn nhất giữa hai thành phố \(u, v\) bất kì không quá \(40\).
• Subtask \(4\) (\(30\%\) số điểm): Không có ràng buộc gì thêm.

Example

12 11 10
12 3
3 2
12 8
8 5
12 11
2 7
12 9
5 1
2 6
12 4
8 10

9