Hướng dẫn giải của Dominative Divide

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tags: Chia để trị, Quy hoạch động

Ý tưởng tổng quát
Xét một đoạn ~[l, r]~, đặt ~m = \lfloor \frac{l + r}{2} \rfloor~. Với mỗi giá trị ~dp_j~ trong khoảng ~[m + 1, r]~, cần tìm vị trí ~i~ sao cho đoạn con ~[i, j]~ không phải là dominative. Sau đó, cập nhật ~dp_j += dp_i~.

Nhận xét

Với đoạn ~[i, j]~ đi qua ~m~ và có giá trị dominative là ~x~, gọi ~u, v~ lần lượt là vị trí đầu tiên và cuối cùng mà ~x~ xuất hiện trong đoạn. Khi đó:

~x~ phải là dominative của ít nhất một trong hai đoạn ~[u, m]~ hoặc ~[m + 1, v]~.
Từ nhận xét này, suy ra rằng:
Một vị trí ~i~ có ~a_i~ là dominative của một đoạn chứa ~i~ khi ~a_i~ là dominative của ~[i, m]~ hoặc ~[m + 1, i]~.
Có thể chứng minh số lượng vị trí ~i~ thoả mãn là ~O(\log(r - l + 1))~.

Từ đó, tập hợp các giá trị ~x~ có khả năng trở thành dominative của một đoạn nào đó đi qua ~m~ được xác định.

Điều kiện dominative của giá trị ~x~

Giả sử ~x~ thuộc tập ứng cử viên. Đặt ~b_i = 1~ nếu ~a_i = x~, và ~-1~ trong trường hợp ngược lại. Khi đó:

~x~ là dominative của đoạn ~[i, j]~ nếu tổng giá trị ~b~ của đoạn lớn hơn ~0~.

Code

const int z = 2e5;

int add(int x, int y) {
    if(y < 0) y += mod; 
    x += y;
    if(x >= mod) x -= mod;
    return x;
}

void calc(int l, int r) {
    if(l >= r) return ;
    int m = (l + r) >> 1;
    calc(l, m);
    int c = 0, mx = 0;
    int init = 0;
    for(int i = m; i >= l; i--) {
        cnt[a[i]]++;
        if(cnt[a[i]] > cnt[mx]) mx = a[i];
        if(cnt[mx] * 2 > (m - i + 1) and !mark[mx]) {
            cand[++c] = mx;
            mark[mx] = 1;
        }
        init = add(init, dp[i - 1]);
    }
    for(int i = m; i >= l; i--) cnt[a[i]]--;
    mx = 0;
    for(int i = m + 1; i <= r; i++) {
        cnt[a[i]]++;
        dp[i] = add(dp[i], init);
        if(cnt[a[i]] > cnt[mx]) mx = a[i];
        if(cnt[mx] * 2 > (i - m) and !mark[mx]) {
            cand[++c] = mx;
            mark[mx] = 1;
        }
    }
    for(int i = m + 1; i <= r; i++) cnt[a[i]]--;
    // cout << l << ' ' << r << ' ' << c << ln;
    for(int i = 1; i <= c; i++) {
        psl[m + 1] = 0;
        int mx = 0, mn = 0;
        for(int j = m; j >= l; j--) {
            psl[j] = psl[j + 1] + (a[j] == cand[i] ? 1 : -1);    
            mx = max(mx, psl[j]);
            mn = min(mn, psl[j]);
        }
        psr[m] = 0;
        for(int j = m + 1; j <= r; j++) {
            psr[j] = psr[j - 1] + (a[j] == cand[i] ? 1 : - 1);
            mx = max(mx, -psr[j]);
            mn = min(mn, -psr[j]);
        }
        for(int j = mn; j <= mx + 1; j++) f[j + z] = 0;
        for(int j = m; j >= l; j--) {
            f[psl[j] + z] = add(f[psl[j] + z], -dp[j - 1]);
            // cout << j << ' ' << psl[j] << ln;
        }
        for(int j = mx; j >= mn; j--) f[j + z] = add(f[j + z], f[j + 1 + z]);
        for(int j = m + 1; j <= r; j++) {
            // cout << j << ' ' << psr[j] << ln;
            dp[j] = add(dp[j], f[z - psr[j] + 1]);
            // cout << j << ' ' << dp[j] << ln;
        }
        mark[cand[i]] = 0;
    }
    calc(m + 1, r);
}