LQDOJ Cup 2024 - Round #4

Cho mảng \(a\) độ dài \(n\): \(a_{1}, a_{2}, \ldots, a_{n}\). Với một dãy con liên tiếp \((l, r)\) \((a_{l}, a_{l + 1}, \ldots, a_{r})\), biến đổi tối giản của nó được định nghĩa là một dãy con liên tiếp \((u, v)\) thỏa mãn:

• \(l \leq u \leq v \leq r\).
• \(min(a_{u}, a_{u + 1}, \ldots , a_{v}) = \min(a_{l}, a_{l + 1}, \ldots, a_{r})\).
• \(max(a_{u}, a_{u + 1}, \ldots , a_{v}) = \max(a_{l}, a_{l + 1}, \ldots, a_{r})\).
• Độ dài của đoạn \((u, v)\) là nhỏ nhất có thể.

Lưu ý: mỗi đoạn con có thể có nhiều biến đổi tối giản.

Bạn sẽ phải trả lời \(q\) truy vấn có dạng:

• \(1\) \(p\) \(x\): đặt \(a_{p} = x\).
• \(2\) \(l\) \(r\): cho biết độ dài và số lượng biến đổi tối giản khác nhau của đoạn \((l, r)\). 2 biến đổi tối giản \((u, v)\) và \((x, y)\) được gọi là khác nhau khi \(u \neq x\) hoặc \(v \neq y\).

Input

• Dòng đầu tiên gồm hai số nguyên \(n\) và \(q\) \((1 \leq n, q \leq 2 \times 10^{5})\).
• Dòng thứ hai gồm \(n\) số nguyên \(a_{1}, a_{2}, \ldots, a_{n}\) \((1 \leq a_{i} \leq 10^{9})\).
• \(q\) dòng tiếp theo gồm các truy vấn:
  • \(1\) \(p\) \(x\) \((1 \leq p \leq n, 1 \leq x \leq 10^{9})\) - miêu tả truy vấn loại \(1\)
  • \(2\) \(l\) \(r\) \((1 \leq l \leq r \leq n)\) - miêu tả truy vấn loại \(2\)
• Dữ liệu vào đảm bảo có ít nhất một truy vấn loại \(2\).

Output

• Với mỗi truy vấn loại \(2\), in ra kết quả của truy vấn đó trên một dòng.

Scoring

• Subtask \(1\) (\(27\%\) số điểm): \(n, q \leq 800\).
• Subtask \(2\) (\(13\%\) số điểm): \(a_{1} \leq a_{2} \leq \ldots \leq a_{n}\) và không có truy vấn loại \(1\).
• Subtask \(3\) (\(15\%\) số điểm): \(a_{1}, a_{2}, \ldots , a_{n}\) là hoán vị của \(1, 2, \ldots, n\) và không có truy vấn loại \(1\).
• Subtask \(4\) (\(19\%\) số điểm): \(q \leq 400\).
• Subtask \(5\) (\(26\%\) số điểm): Không có ràng buộc gì thêm.

Example

10 9
4 7 5 3 4 4 3 4 8 5
2 4 8
1 2 8
2 1 10
1 7 8
2 3 9
1 8 3
2 1 10
1 1 2
2 1 10

2 3
3 2
4 1
2 2
2 1

Cho \(m\) cái hộp được chia vào \(n\) dãy hộp, dãy thứ \(i\) gồm \(a_{i}\) cái hộp có màu \(i\) và được đánh số thứ tự từ \(1\) đến \(a_{i}\).

Mỗi một bước, ta có thể chọn \(2\) hộp \(x\) và \(y\) lần lượt thuộc dãy hộp \(i\) và \(j\) \((1 \leq x \leq a_{i}, 1 \leq y \leq a_{j})\) và đổi vị trí \(2\) cái hộp đó.

Sau một số bước, các dãy hộp phải thỏa mãn điều kiện với \(1 \leq i \leq n\), dãy thứ \(i\) không được chứa bất kì cái hộp nào có màu \(i\).

Hỏi có bao nhiêu cách sắp xếp khác nhau của những dãy hộp biết \(2\) cách sắp xếp được xem là khác nhau nếu tồn tại \(u\) và \(v\) \((1 \leq v \leq n, 1 \leq u \leq a_{v})\) sao cho cái hộp thứ \(u\) của dãy thứ \(v\) của 2 cách sắp xếp đó khác màu hoặc khác số thứ tự.

Input

• Dòng đầu tiên gồm hai số nguyên dương \(n\) và \(m\) \((2 \leq n \leq 500, 2 \leq m \leq 1000)\).
• Dòng thứ hai gồm \(n\) số nguyên dương \(a_{1}, a_{2}, \ldots, a_{n}\) \((1 \leq a_{i} \leq m)\).
• Dữ liệu vào luôn đảm bảo \(\sum_{i = 1}^n{a_{i}} = m\).

Output

• In ra một số duy nhất là kết quả của bài toán modulo \(998244353\).

Scoring

• Subtask \(1\) (\(15\%\) số điểm): \(n, m \leq 10\).
• Subtask \(2\) (\(20\%\) số điểm): \(n, m \leq 20\).
• Subtask \(3\) (\(20\%\) số điểm): \(a_{i} = 1\) với \(1 \leq i \leq n\).
• Subtask \(4\) (\(15\%\) số điểm): \(a_{i} = 2\) với \(1 \leq i \leq n\).
• Subtask \(5\) (\(30\%\) số điểm): Không có ràng buộc gì thêm.

Example

3 4
1 1 2

4

3 5
1 2 2

16

Trong vườn nhà Bin có \(n\) con khỉ sống trong \(n\) tòa tháp được xếp liên tiếp nhau trên một đường thẳng, các tòa tháp được đánh số từ \(1\) đến \(n\). Chiều cao của tòa tháp thứ \(i\) là \(h_{i}\) mét.

Mỗi tòa tháp đều có duy nhất một cửa sổ nhỏ ở tầng trên cùng để quan sát. Con khỉ ở toà tháp \(i\) sẽ chỉ nhìn thấy con khỉ khác ở tòa tháp \(j\) nếu độ cao hai tòa tháp này bằng nhau \((h_{i} = h_{j})\) và mọi tòa tháp ở giữa đều thấp hơn hai tòa tháp này (\(h_{k} < h_{i} \forall \min(i, j) < k < \max(i, j)\)).

Để tránh việc một số con khỉ trở nên cô đơn và nổi loạn, mỗi con khỉ cần phải nhìn thấy một con khỉ khác để có thể giao tiếp. Bin muốn chia \(n\) con khỉ thành \(\dfrac{n}{2}\) cặp, sao cho các con khỉ được ghép cặp có thể nhìn thấy nhau và mỗi con khỉ được ghép với đúng một con khỉ khác.

Bin nhận thấy rằng với các tòa tháp hiện tại thì có thể không tồn tại cách ghép cặp nào cho các con khỉ thỏa mãn yêu cầu kể trên. Tuy nhiên, cậu có thể thực hiện một số thao tác để thay đổi chiều cao của các tòa nhà. Mỗi thao tác Bin có thể chọn nâng một tòa tháp thêm độ cao \(1\) mét.

Hãy giúp Bin tính số thao tác ít nhất cần thiết sao cho tồn tại cách để có thể ghép cặp cho các con khỉ.

Input

• Dòng đầu tiên gồm một số nguyên \(T\) là số bộ test. \(T\) nhóm dòng sau, mỗi nhóm dòng thể hiện một test:
  • Dòng đầu gồm một số nguyên dương \(n\) \((1 \leq n \leq 3 \times 10^{5})\). Dữ liệu đảm bảo \(n\) luôn chẵn.
  • Dòng thứ hai gồm \(n\) số nguyên \(h_{1}, h_{2}, \ldots, h_{n}\) \((1 \leq h_{i} \leq 10^{9})\).
• Dữ liệu đảm bảo \(N \leq 3 \times 10^{5}\), với \(N\) là tổng các giá trị \(n\) trong tất cả các bộ test.

Output

• Gồm \(T\) dòng, dòng thứ \(i\) gồm một số duy nhất là kết quả của test thứ \(i\).

Scoring

• Subtask \(1\) (\(21\%\) số điểm): \(N \leq 30\).
• Subtask \(2\) (\(23\%\) số điểm): \(N \leq 300\).
• Subtask \(3\) (\(27\%\) số điểm): \(N \leq 1000\).
• Subtask \(4\) (\(29\%\) số điểm): Không có ràng buộc gì thêm.

Example

3
4
1 3 6 2
8
4 5 1 4 1 3 6 6
18
2 4 5 2 1 1 4 6 3 5 3 6 5 4 3 5 3 6

6
6
14