Kinh Nghiệm về M m0 sqrt 1-v 2 c 2 vì sao Mới Nhất

Bạn đang tìm kiếm từ khóa M m0 sqrt 1-v 2 c 2 vì sao được Cập Nhật vào lúc : 2022-08-04 21:05:16 . Với phương châm chia sẻ Bí kíp về trong nội dung bài viết một cách Chi Tiết 2022. Nếu sau khi đọc tài liệu vẫn ko hiểu thì hoàn toàn có thể lại phản hồi ở cuối bài để Ad lý giải và hướng dẫn lại nha.

Tác giả: Nguyễn RR Thành Trung

Nội dung chính

    Thuật toán MoMở rộngCải tiếnBài tập áp dụngVideo liên quan

Tiếp nối chuỗi nội dung bài viết về những thuật toán chia căn, trong nội dung bài viết này toàn bộ chúng ta sẽ bàn về kĩ thuật tăng vận tốc vấn đáp truy vấn bằng phương pháp sắp xếp chúng theo một thứ tự nhất định, còn gọi là Mo’s algorithm.

Bài toán

Cho một dãy số $A$ gồm $N$ thành phần. Cần thực thi $Q.$ truy vấn, mỗi truy vấn $(i, j)$ yêu cầu tìm $mode(A_i, …, A_j)$. (Mode của một tập hợp là giá trị xuất hiện nhiều lần nhất trong tập hợp đó). Giới hạn: $N, Q., A_i le 10^5$.

Khi đọc đề một bài toán truy vấn kiểu này, có lẽ rằng CTDL thứ nhất mà những bạn nghĩ đến là Interval Tree. Nhưng có điều gì đó không ổn trong bài này: Khi có thông tin của 2 nút con $[l, mid]$ và $[mid+1, r]$, rất khó để tìm kiếm được bất kỳ thông tin hữu ích nào của $[l, r]$.

Duyệt

Chúng ta xuất phát từ thuật toán duyệt hồn nhiên như sau:

    Với mỗi truy vấn, ta for từ trái sang phải, đếm số lần xuất hiện.
    Trong khi đếm thì ta update kết quả.

Code đơn thuần và giản dị như sau:

function mode(l, r): // Khởi tạo mảng count = toàn 0 res = -1; for i = l .. r: count[A[i]] += 1; if res == -1 or count[A[i]] > count[res]: res = A[i]; return res;

Dễ thấy, thuật toán duyệt này còn có độ phức tạp $O(N * Q.)$. Có 2 nguyên do chính khiến thuật toán này chạy chậm:

Khởi tạo mảng count mỗi lần mất $O(N)$.
Với mỗi truy vấn, phải tính lại mảng count từ trên đầu.

Ta hoàn toàn có thể tăng cấp cải tiến được như sau:

Sau khi vấn đáp truy vấn $[l_1, r_1]$, để vấn đáp truy vấn $[l_2, r_2]$, bạn chỉ việc thay đổi mảng đếm một cách thích hợp. Cụ thể:

    Nếu $l_2 > l_1$, giảm số lần xuất hiện của $A_l_1, …, A_l_2-1$
    Nếu $l_2 < l_1$, tăng số lần xuất hiện của $A_l_2, …, A_l_1-1$
    Tương tự với $r_1$ và $r_2$.

Để update số lần xuất hiện lớn số 1 thì hoàn toàn có thể dùng thêm set.

Như vậy, độ phức tạp của ta là tổng $|l_i – l_i-1| + |r_i – r_i-1|$, nhân thêm $mathcalO(logN)$ để đếm và tìm thành phần lớn số 1 của mảng đếm.

Thuật toán Mo

Thuật toán Mo là một cách sắp xếp lại những truy vấn, sao cho tổng $|l_i – l_i-1| + |r_i – r_i-1|$ không thật $O(N * sqrtN + Q. * sqrtN)$.

Thứ tự những truy vấn được định nghĩa qua hàm so sánh dưới đây.

S = sqrt(N);
bool cmp(Query A, Query B) // so sánh 2 truy vấn
if (A.l / S != B.l / S) return A.l / S < B.l / S; return A.r < B.r;

Giải thích:

    Ta chia dãy thành những block (nhóm) độ dài $S = sqrtN$.
    Nếu đầu trái của truy vấn nằm ở vị trí 2 block rất khác nhau, ta sắp xếp theo đầu trái.
    trái lại (đầu trái của truy vấn nằm ở vị trí cùng 1 block), ta sắp xếp theo đầu phải.

Chứng minh:

Mo’s algorithm có độ phức tạp là $O(N * sqrtN + Q. * sqrtN)$. Để hiểu tại sao độ phức tạp của thuật toán đạt được như vậy, toàn bộ chúng ta hãy cùng xem việc di tán những đoạn $[l_1,r_1]$ thành $[l_2,r_2]$:

    Di chuyển $l_1 rightarrow l_2$:

      Nếu $l_1$ và $l_2$ cùng block: Với mỗi thao tác, độ phức tạp không thật $sqrtN$. Do đó, độ phức tạp trong trường hợp này của toàn bộ $Q.$ thao tác là $O(Q. * sqrtN)$.
      Nếu $l_1$ và $l_2$ khác block: Vì ta ưu tiên sort theo block chứa $l$, nên trường hợp này xẩy ra không thật $sqrtN$ lần. Ở trường hợp này, ta mất độ phức tạp tối đa là $O(N)$, nên với toàn bộ những thao tác, độ phức tạp là $O(N * sqrtN)$.

    Di chuyển $r_1 rightarrow r_2$:

      Nếu $l_1$ và $l_2$ cùng block: Vì trong cùng một block $r$ được sắp xếp tăng dần, nên với mỗi block của $l$, ta chỉ mất độ phức tạp tổng là $O(N)$. Do có $sqrtN$ block rất khác nhau của $l$, nên tổng độ phức tạp trong trường hợp này là $O(N * sqrtN)$.
      Nếu $l_1$ và $l_2$ khác block: Như trên đã phân tích, ta chỉ có $sqrtN$ lần đổi block, mỗi lần đổi block ta mất độ phức tạp $O(N)$ để di tán $r$. Do đó tổng độ phức tạp của trường hợp này là $O(N * sqrtN)$.

Vậy, độ phức tạp là $O(N * sqrtN + Q. * sqrtN)$.

Áp dụng

Sử dụng Mo’s Algorithm, bạn đã hoàn toàn có thể thu được một thuật toán hoàn hảo nhất cho bài này với độ phức tạp $O(N * sqrtN + Q. * sqrtN)$:

    Sort toàn bộ những truy vấn theo Mo’s Algorithm.
    Gọi $S(N)$ là một mảng gồm $N$ set (hoàn toàn có thể cài bằng hash table (bảng băm)). $S(i)$ chứa toàn bộ những số xuất hiện đúng $i$ lần.
    Gọi $A(val)$ = số lần xuất hiện của val.
    Đặt $max$ là chỉ số lớn số 1 của mảng $S$ mà $S(max)$ khác rỗng.
    Ta sẽ thêm và xóa một số trong những trong O(1) như sau:

      Thêm 1 số $v$:

        Xóa $v$ khỏi $S(A(v))$.
        Tăng $A(v)$ thêm một.
        Thêm $v$ vào $S(A(v))$.
        Nếu $A(v) > max$, update $max$.

      Xóa 1 số $v$:

        Xóa $v$ khỏi $S(A(v))$.
        Giảm $A(v)$ đi 1.
        Thêm $v$ vào $S(A(v))$.
        Nếu $S(max)$ rỗng, giảm $max$ đi 1.

Vì tổng những thao tác thêm và xóa khi vận dụng Mo’s Algorithm không thật $O(N * sqrtN + Q. * sqrtN)$, ta thu được một thuật toán với độ phức tạp này.

Mở rộng

Với mục tiêu làm bài toán khó hơn, ta xét trường hợp mà CTDL của ta chỉ được cho phép thực thi đúng 2 thao tác:

    Insert: Thêm 1 thành phần vào CTDL, thao tác này còn có độ phức tạp là $O(logN)$ hoặc $O(1)$.

    Snapshot: Lưu lại trạng thái hiện tại của CTDL. Thao tác này còn có độ phức tạp $O(N)$.

    Rollback: Hồi phục lại trạng thái của CTDL ở lần Snapshot cuối. Thao tác này cũng luôn có thể có độ phức tạp là $O(N)$.

Một ví dụ của CTDL loại này là Disjoint set, và việc xử lý truy vấn xuất hiện trong bài toán Codechef – GERALD07.

Cách làm vẫn là vận dụng Mo’s algorithm, tuy nhiên vì không thể xóa thành phần, nên ta không thể di tán từ $l_1$ sang $l_2$ một cách thuận tiện và đơn thuần và giản dị được.

Để đơn thuần và giản dị, toàn bộ chúng ta chỉ xét những truy vấn $[l, r]$ mà $l$ và $r$ rơi vào 2 block rất khác nhau. Để xử lý và xử lý việc không di tán ngược được, sau khi vấn đáp truy vấn $[l, r]$, toàn bộ chúng ta cần dùng Rollback để lấy l về cuối block chứa l. Sau đó, khi vấn đáp truy vấn $[l_2, r_2]$, toàn bộ chúng ta chỉ việc thực thi Insert từ $r+1$ đến $r_2$ và từ $l_2$ đến cuối block chứa $l_2$.

Chi tiết setup:

rt = sqrt(n); init(); // this initializes our data structure (clears it) snapshot(); for all queries q if q.r – q.l + 1 <= rt + 1 // we process light queries for j := q.l to q.r insert(j); store answer for query q; rollback(); last_bucket = -1; for all queries q if q.r – q.l + 1 <= rt + 1: continue; bucket = q.l / rt; if bucket != last_bucket init(); l = (bucket + 1) * rt; // right border of the bucket r = q.r; for j := l to r insert(j); last_bucket = bucket; while r < q.r insert(++r); snapshot(); for j := q.l to l – 1 insert(j); store answer for query q; rollback();

Cải tiến

Các bạn hoàn toàn có thể đọc thêm về kiểu cách tăng cấp cải tiến vận tốc chạy của Mo sử dụng TSP và Hilbert curve tại đây.

Bài tập vận dụng

    Codeforces Yandex 2011 Round 2 – D
    Codechef – GERALD07

Reply
8
0
Chia sẻ

4464

Review M m0 sqrt 1-v 2 c 2 vì sao ?

Bạn vừa đọc Post Với Một số hướng dẫn một cách rõ ràng hơn về Video M m0 sqrt 1-v 2 c 2 vì sao tiên tiến và phát triển nhất

Share Link Cập nhật M m0 sqrt 1-v 2 c 2 vì sao miễn phí

You đang tìm một số trong những Chia Sẻ Link Cập nhật M m0 sqrt 1-v 2 c 2 vì sao Free.

Giải đáp vướng mắc về M m0 sqrt 1-v 2 c 2 vì sao

Nếu sau khi đọc nội dung bài viết M m0 sqrt 1-v 2 c 2 vì sao vẫn chưa hiểu thì hoàn toàn có thể lại phản hồi ở cuối bài để Mình lý giải và hướng dẫn lại nha
#sqrt #vì #sao