Editorial for Dominative Divide

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

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);
}