DSU

[vzsky]

statement

ให้ list A ของจำนวนเต็ม n ตัว และให้จำนวนเต็มอีก k ตัว
แทรก k ตัวนั้นไปที่ไหนก็ได้ใน A เพื่อสร้าง B
Define f(B, u) เป็นจำนวนของคู่ (u, v) ที่ เมื่อพิจารณา B ในช่วง u ถึง v (หรือ v ถึง u) จะได้ว่าค่ามากสุดของช่วงนั้นอยู่ที่ u
ถามว่า max Sum(f(B, u)) คืออะไร

concept

Sorting + DSU -> O((n+k)log(n+k)) (มั้ง)

[vzsky]

subtasks

• k = 0 & O(n^2) -> วนทุก u v เช็ค
• k = 1 & O(n^3) -> วนทุก uv ในทุก B ที่เป็นไปได้
• k = 0 & O(n) -> stack
• k = 1 & O(n^2) -> stack ในทุก B ที่เป็นไปได้
• O((n+k)^2) -> sort แล้ว add น้อยไปมาก แต่ไม่ใช้ dsu
• O((n+k)log(n+k)) -> sort + dsu