TKPC - Song Sư vs Tam Kiệt

Cho xâu \(S\) độ dài \(N\) chỉ chứa các chữ cái latin in thường, các ký tự được đánh chỉ số từ \(1\). Hãy lập trình xử lý lần lượt \(Q\) truy vấn ở hai loại sau:

• Loại \(1\): Thay đổi ký tự thứ \(i\) của \(S\) thành \(c\) (không làm gì cả nếu \(S_i=c\) sẵn).
• Loại \(2\): Đếm số lượng ký tự phân biệt xuất hiện trong xâu con từ vị trí \(l\) đến vị trí \(r\) của \(S\).

Input

• Dòng đầu chứa số nguyên dương \(N\) \((N\leq 5\cdot 10^5)\).
• Dòng tiếp theo chứa xâu \(S\) bao gồm \(N\) ký tự latin in thường.
• Dòng tiếp theo chứa số nguyên dương \(Q\) \((Q\leq 2\cdot 10^4)\).
• \(Q\) dòng tiếp theo có dạng 1 i c hoặc 2 l r thể hiện một truy vấn ở thể loại tương ứng.

Output

• Với mỗi truy vấn loại \(2\), in ra số lượng ký tự phân biệt cần tìm.

Example

7
abcdbbd
6
2 3 6
1 5 z
2 1 1
1 4 a
1 7 d
2 1 7

3
1
5

Cho \(A+B+C\) lá bài, trong đó có đúng \(A\) lá bài được ghi số \(1\), có đúng \(B\) lá bài ghi số \(0\) và \(C\) lá bài ghi số \(-1\). Bạn hãy lập trình chọn ra \(K\) lá bài trong số chúng để tổng các số được ghi trên các lá bài là lớn nhất có thể.

Input

• Một dòng duy nhất chứa bốn số nguyên \(A\), \(B\), \(C\) và \(K\).
• \(0\leq A, B, C\).
• \(1\leq K\leq A+B+C\leq 2\cdot 10^9\).

Output

In ra tổng lớn nhất tìm được.

Ví dụ

2 1 1 3

2

1 2 3 4

0

2000000000 0 0 2000000000

2000000000

Oanh Trúc Béo muốn đi phát quà liên khối cho \(n\) học sinh khối chuyên Tin. Các học sinh này đều đứng trên trục số và được đánh số lần lượt từ \(1\) đến \(n\), học sinh thứ \(i\) đứng ở tọa độ \(p_i\). Oanh Trúc đứng ở gốc tọa độ (điểm \(0\)) và muốn tìm một trình tự phát quà để tổng độ bất mãn của \(n\) học sinh này là nhỏ nhất có thể, biết rằng Oanh Trúc cần đúng \(1\) phút để di chuyển được một đơn vị độ dài trên trục số, đồng thời, nếu học sinh nào chưa được nhận quà, thì cứ mỗi phút trôi qua, độ bất mãn của bạn ấy sẽ tăng lên \(1\) (độ bất mãn ban đầu của mỗi người đều bằng \(0\)).

Các bạn hãy lập trình tính toán giúp Oanh Trúc độ bất mãn nhỏ nhất có thể nhé!

Input

• Dòng đầu chứa số nguyên dương \(n\) \((n\leq 1000)\).
• Dòng tiếp theo chứa \(n\) số nguyên \(p_1\), \(p_2\),..., \(p_n\) \(\left(-5\cdot 10^5\leq p_i\leq 5\cdot 10^5\right)\).

Output

• Tổng độ bất mãn nhỏ nhất có thể.

Example

4
-2 -12 3 7

50

Cho dãy số nguyên \(A\) gồm \(N\) phần tử \(A_1\), \(A_2\),..., \(A_N\), ta định nghĩa độ khó chịu của một đoạn con \([L, R]\) là giá trị \(\max(A[L], A[L+1],..., A[R])-\min(A[L], A[L+1],..., A[R])\). Hãy lập trình xác định đoạn con có độ khó chịu nhỏ nhất trong số các đoạn con \([L, R]\) với \(1\leq L < R\leq N\) của dãy \(A\).

Input

• Dòng đầu chứa số nguyên dương \(N\) \((2\leq N\leq 10^5)\).
• Dòng thứ hai chứa \(N\) số nguyên mô tả dãy \(A\). Các số đều có giá trị tuyệt đối không vượt quá \(10^9\).

Output

• Một số nguyên là độ khó chịu nhỏ nhất tìm được.

Example

2
1 3

2

3
1 1 1

0

5
1 2 1 2 1

1

Lớp ITK19 có \(n\) học sinh nam, mỗi học sinh nam này đều crush đúng một trong ba bạn nữ: Oanh Trúc, Hương An và Tuyết Ny. Hoàng Hải từng khai thác hết thông tin crush-ship của từng bạn nam trong \(n\) bạn này và ghi chép hết chúng vào một cuốn sổ tay. Thật không may, Hải vừa đánh mất cuốn sổ của mình và rất tiếc nuối các thông tin quý giá mà mình đã dày công sưu tầm. Anh ấy chỉ còn nhớ đúng \(m\) thông tin: mỗi thông tin có dạng S u v hoặc D u v, trong đó, S u v đồng nghĩa với việc học sinh \(u\) và học sinh \(v\) cùng crush chung một người, còn D u v thể hiện rằng \(u\) và \(v\) crush hai người khác nhau.

Hải cho bạn biết \(m\) thông tin đó và nhờ bạn lập trình tính toán giúp có bao nhiêu trạng thái crush-ship thỏa mãn các ràng buộc mà anh đã nêu ra. Hãy giúp Hải nhé!

Input

• Dòng đầu chứa hai số nguyên dương \(n\) và \(m\) (\(n\leq 15\), \(m\leq 50\)).
• Mỗi dòng trong \(m\) dòng tiếp theo có dạng S u v hoặc D u v thể hiện một ràng buộc tương ứng.

Output

• Một số nguyên duy nhất là số trạng thái crush-ship thỏa mãn.

Example

4 2
S 1 2
D 1 3

18

Cho dãy số nguyên dương \(A\) gồm \(N\) phần tử. Một phần tử \(A_i\) được gọi là phần tử đẹp nếu nó thỏa mãn điều kiện: không tồn tại chỉ số \(j\) nào (\(1\leq j\leq N\), \(j\neq i\)) mà \(A_i\) chia hết cho \(A_j\). Bạn hãy lập trình tính số phần tử đẹp của dãy \(A\) nhé!

Input

• Dòng đầu chứa số nguyên dương \(N\) \((N\leq 2\cdot 10^5)\).
• Dòng tiếp theo chứa \(N\) số nguyên dương \(A_1, A_2, \ldots, A_N\) \((A_i\leq 10^6)\). Lưu ý rằng một số phần tử trong dãy \(A\) có thể trùng nhau.

Output

• Một số nguyên duy nhất là số phần tử đẹp.

Example

5
24 11 8 3 16

3

4
5 5 5 5

0

10
33 18 45 28 8 19 89 86 2 4

5