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