Trước đó em đang làm bài này PATULJCI thì bí. Giờ nhờ bài của anh em đã có thể làm được nhưng khi em nộp lại bị lỗi RE , vẫn chưa biết sai chỗ nào, nhờ anh (cũng như mọi người) giúp với (vì bài đầu tiên làm mà sai thì hơi chán). 

Bài của em : link.

Để em nói tóm tắt đề như sau : Cho mảng N <= 3e5 phần tử, cho M <= 1e5 truy vấn, mỗi truy vấn là L...R, yêu cầu kiểm tra xem số xuất hiện nhiều lần nhất có lớn hơn một nửa số phần từ của đoạn này không, nếu không thỏa thì puts ra no, trái lại puts yes và số đó 

Trong bài của em :

• hàm Insert và Erase là chỗ thêm phần tử và xóa phần tử,

• em dùng set chứ ko dùng hash table,

• mảng ans[] là trả lời cho các truy vấn,

• trong Query có L, R là đoạn của truy vấn, id là chỉ số truy vấn,

• trong phần giải quyết các truy vấn, em thêm cả đoạn l1...r1 vào trước, sau đó với mỗi truy vấn i > 1, em tính giá trị của truy vấn i-1 trước , sau đó mới cập nhật truy vấn i 

Còn nữa, bài này Codeforces Yandex 2011 Round 2 - D em cũng thử làm và cũng bị RE. Hy vọng admin cũng như mọi người giúp đỡ. Link.

Em đã tìm ra được chỗ sai (chỗ xét vị trí L,R của hai truy vấn kề nhau bị nhầm một chút), nhưng sau khi sửa lại, em vẫn vị RE

Bài PATULJCI có một cách khá hay như sau, lưu ý là đề bài hỏi có tồn tại một số xuất hiện nhiều hơn một nửa không chứ không phải là tìm số xuất hiện nhiều lần nhất.

Để kiểm tra một khoảng có thỏa mãn đề bài, trước hết bạn cần một hàm đếm xem một số bất kì xuất hiện trong khoảng bao nhiêu lần, hàm này mất O(log N). Sau đó, thử khoảng 20 lần, mỗi lần random một số thuộc khoảng và đếm xem số đó xuất hiện bao nhiêu lần trong khoảng. Nếu random trúng số xuất hiện hơn một nửa thì khoảng thỏa mãn luôn, còn sau 20 lần mà không được số nào thì coi là không thỏa mãn.

Xác suất: Thuật toán sẽ sai nếu như khoảng đó thỏa mãn, mà sau cả 20 lần random không trúng được số xuất hiện hơn một nửa. Nếu khoảng thỏa mãn thì có một số xuất hiện hơn một nửa, xác suất để random trúng số đó là 1/2. Xác suất để random hỏng cả 20 lần là 1/2^20 -> Xác suất để đúng là 1 - 1/2^20 = 0.999999. Bạn cần trả lời 100000 câu, xác suất để đúng hết là 0.999999^100000 = 0.9 (thực tế là còn cao hơn nhiều vì không phải câu hỏi nào cũng là khoảng thỏa mãn và số số xuất hiện nhiều nhất chính xác là một nửa).

Độ phức tạp là O(C * log N * Số lần thử).

Ý tưởng của anh hay quá, chỉ cái xác suất thôi là em đã like cho anh một cái. Nhưng mà em vẫn chưa nghĩ ra làm sao đếm một số xuất hiện bao nhiêu lần trong O(logN).

Em vẫn đang chờ đợi ai đó chỉnh giúp em Mo's Algorithm, thuật này em mới biết và thấy khá hay

Trước đó em đang làm bài này PATULJCI thì bí. Giờ nhờ bài của anh em đã có thể làm được nhưng khi em nộp lại bị lỗi RE , vẫn chưa biết sai chỗ nào, nhờ anh (cũng như mọi người) giúp với (vì bài đầu tiên làm mà sai thì hơi chán). 

Bài của em : link.

Để em nói tóm tắt đề như sau : Cho mảng N <= 3e5 phần tử, cho M <= 1e5 truy vấn, mỗi truy vấn là L...R, yêu cầu kiểm tra xem số xuất hiện nhiều lần nhất có lớn hơn một nửa số phần từ của đoạn này không, nếu không thỏa thì puts ra no, trái lại puts yes và số đó 

Trong bài của em :

• hàm Insert và Erase là chỗ thêm phần tử và xóa phần tử,

• em dùng set chứ ko dùng hash table,

• mảng ans[] là trả lời cho các truy vấn,

• trong Query có L, R là đoạn của truy vấn, id là chỉ số truy vấn,

• trong phần giải quyết các truy vấn, em thêm cả đoạn l1...r1 vào trước, sau đó với mỗi truy vấn i > 1, em tính giá trị của truy vấn i-1 trước , sau đó mới cập nhật truy vấn i 

Còn nữa, bài này Codeforces Yandex 2011 Round 2 - D em cũng thử làm và cũng bị RE. Hy vọng admin cũng như mọi người giúp đỡ. Link.

Em đã tìm ra được chỗ sai (chỗ xét vị trí L,R của hai truy vấn kề nhau bị nhầm một chút), nhưng sau khi sửa lại, em vẫn vị RE

1 lý do khiến bạn bị RE có thể là do dùng quá nhiều bộ nhớ

Bài này có 2 cách làm:

Cách 1: Giả sử 1 dãy số tồn tại số xuất hiện nhiều hơn 1 nữa số lượng phần tử. Nếu ta cứ thực hiện thao tác xóa 2 khác nhau đi cho tới khi chỉ còn số cùng 1 giá trị xuất hiện thì số đó chính là số cần tìm. Với tư tưởng này ta có thể áp dụng IT vào bài toán, trong đó mỗi nút quản lí 1 đoạn L..R sẽ chứa 2 giá trị: số lượng số còn lại nếu thực hiện việc chọn 2 số khác nhau và xóa đi trong đoạn L..R và giá trị của số này. Với 2 nút con IT chứa 2 giá trị trên ta có thể tính được 2 giá trị tương ứng cho nút cha một cách dễ dàng. Sau khi dựng xong cây IT thì với mỗi truy vấn ta tính 2 giá trị đó cho các nút quản lí các đoạn con thuộc vùng truy vấn, dựa vào 2 giá trị đó để tìm kq. Bạn có thể tham khảo lời giải này chi tiết hơn tại đây: http://hsin.hr/coci/archive/2009_2010/contest3_solutions.zip

Cách 2: Cách này đơn giản hơn nhiều và dựa trên tính chất của xác suất, giả sử đoạn L..R có tồn tại 1 giá trị xuất hiện nhiều hơn 1 nữa số lượng phần tử trong đoạn, nếu ta chọn ngẫu nhiên 1 số thì xác suất để chọn trúng giá trị đó là hơn 50%. Do đó theo tính chất xác suất thì cứ 2 lần chọn thì sẽ có thể chọn trúng số có giá trị cần tìm, sau khi chọn được 1 số ta có thể đếm số lần xuất hiện của số đó trong đoạn L..R trong O(log) bằng cách lưu vị trí xuất hiện của từng loại giá trị theo thứ tự tăng dần. Tóm lại cách làm khá đơn giản: Với mỗi truy vấn, cứ lặp lại tầm 30 lần, chọn random 1 số trong đoạn L..R có giá trị x, đếm xem trong đoạn L..R số lần xuất hiện của x có lớn hơn 1 nữa số phần tử hay không. Nếu có thì xuất ra yes, nếu sau 10 lần mà không tìm được giá trị nào thỏa điều kiện thì xuất ra no. Thuật toán này sẽ có xác suất bị sai nhưng khá thấp. Xác suất bị sai cho 1 bộ test nếu dùng phương pháp này là khoảng (Q / 2^30), tức là tầm khoảng. 0.001%. Ta có thể tăng số lần lặp lên để giảm xác suất sai hơn nữa.

Bài PATULJCI có một cách khá hay như sau, lưu ý là đề bài hỏi có tồn tại một số xuất hiện nhiều hơn một nửa không chứ không phải là tìm số xuất hiện nhiều lần nhất.

Để kiểm tra một khoảng có thỏa mãn đề bài, trước hết bạn cần một hàm đếm xem một số bất kì xuất hiện trong khoảng bao nhiêu lần, hàm này mất O(log N). Sau đó, thử khoảng 20 lần, mỗi lần random một số thuộc khoảng và đếm xem số đó xuất hiện bao nhiêu lần trong khoảng. Nếu random trúng số xuất hiện hơn một nửa thì khoảng thỏa mãn luôn, còn sau 20 lần mà không được số nào thì coi là không thỏa mãn.

Xác suất: Thuật toán sẽ sai nếu như khoảng đó thỏa mãn, mà sau cả 20 lần random không trúng được số xuất hiện hơn một nửa. Nếu khoảng thỏa mãn thì có một số xuất hiện hơn một nửa, xác suất để random trúng số đó là 1/2. Xác suất để random hỏng cả 20 lần là 1/2^20 -> Xác suất để đúng là 1 - 1/2^20 = 0.999999. Bạn cần trả lời 100000 câu, xác suất để đúng hết là 0.999999^100000 = 0.9 (thực tế là còn cao hơn nhiều vì không phải câu hỏi nào cũng là khoảng thỏa mãn và số số xuất hiện nhiều nhất chính xác là một nửa).

Độ phức tạp là O(C * log N * Số lần thử).

cảm ơn anh nhiều ạ !

Nhưng em vẫn muốn hỏi liệu như 'thuật Mo' có áp dụng được cho bài này, và cả  Codeforces Yandex 2011 Round 2 - D  nữa.

Em đã tìm ra một lỗi khiến RE, và em đã sửa lại nhưng vẫn RE test 6. Theo RR bảo rằng do dùng quá nhiều bộ nhớ, liệu có cách nào cải thiện chăng ?

Link submit bài codeforces http://codeforces.com/contest/86/submission/11943308