Village Solution

--- author: little tags: Village title: Village Solution --- $\Huge\text{Village Solution}$ ------- :::info 📌 Tags: `hld` `data structure` `sieve` `hash` ✍️ Writer: little 📋 Content: [TOC] ::: ----- ## Thuật toán Vấn đề khó khăn nhất trong bài toán này là làm sao để kiểm tra xem $2$ làng này có các mức độ tôn giáo giống hệt nhau hay không? Có một cách để kiểm tra điều kiện đó trong độ phức tạp $O(1)$ khá hay. Đó là ban đầu cũng ta sẽ nén các mức độ tôn giáo lại. Ví dụ như các mức độ tôn giáo lần lượt là $3,1,6,7,4,6,1$ thì sau khi nén chúng sẽ trở thành $2,1,4,5,3,4,1$. Bởi vì ta chỉ cần kiểm tra xem các mức độ tôn giáo có giống nhau hay không nên việc nén lại không ảnh hưởng gì đến kết quả của bài toán. Ta có một mảng $val_u$ là số để biểu thị các mức độ tôn giáo của làng $u$. Sau khi nén lại như vậy thì với mỗi tôn giáo $t$ (sau khi nén) đi qua làng $u$, ta sẽ cập nhật $val_u *= prime(t)$ với $prime(t)$ là số nguyên tố thứ $t$. Tức là $val_u$ của ta sẽ có dạng là $a^x*b^y*c^z*...$ với $a,b,c$ là các số nguyên tố và $x,y,z$ là số lần xuất hiện của số nguyên tố đó. Ở trong bài này $a,b,c$ tương ứng với các loại tôn giáo còn $x,y,z$ tương ứng là bậc của loại tôn giáo đó. Cách lưu này dựa trên ý tưởng của thuật toán $hash$. Và vì $val_u$ có thể rất lớn nên ta sẽ $mod$ chúng cho một số $mod$ nào đó đủ lớn ví dụ như $1e9+7$ hoặc $998244353$. Nó vẫn có xác suất sai nhưng cực kì nhỏ. Khi đã tạo được mảng $val$ như vậy thì ta đã có thể kiểm tra $2$ làng có cùng các mức độ tôn giáo hay không trong $O(1)$ rồi. Việc còn lại là làm sao để xử lí cập nhật và truy vấn trong $O(log(n))$. Và cách làm là chúng ta sẽ sử dụng cấu trúc dữ liệu $Segment$ $Tree$. Với mỗi truy vấn cập nhật thì ta sẽ nhân một đoạn lên $prime(t)$ đơn vị (dùng $lazy$). $Segment$ $Tree$ của ta sẽ lưu thêm một biến $bool$ để kiểm tra xem tất cả giá trị trong đoạn này có giống nhau hay không. Như vậy thì với truy vấn loại $2$ thì ta chỉ cần kiểm tra xem trên đoạn đó có $true$ hết không là được. Đến đây thì bạn đã làm được đến $subtask$ $3$ rồi. Muốn $AC$ thì việc còn lại là kết hợp thêm thuật toán [$hld$](https://vnoi.info/wiki/algo/data-structures/heavy-light-decomposition.md) để $AC$ thôi :D. ---- Tham khảo code ở [đây](https://ideone.com/slbTmE)