P11673 [USACO25JAN] Median Heap G 題解
題目傳送門(mén)
題目大意
對(duì)于一顆完全二叉樹(shù)，定義其節(jié)點(diǎn) \(u\) 的
- 左兒子 \(ls=u\times2\)，右兒子 \(rs=u\times2+1\)
- 父親為 \(\lfloor \frac u2\rfloor\)
- 置換操作：將 \(u\) 的值換為 \(\{u,\) \(ls\)(如果有), \(rs\)(如果有)\(\}\) 的中位數(shù)，代價(jià)為 \(\text0\)
- 修改操作：將 \(u\) 的值修改為任意數(shù)，代價(jià)為 \(c_u\)
- “近似中位數(shù)”：從最后一個(gè)節(jié)點(diǎn) \(n\) 開(kāi)始向前執(zhí)行，若此節(jié)點(diǎn)非葉子節(jié)點(diǎn)，則進(jìn)行置換操作，最后節(jié)點(diǎn) \(1\) （根）的值即為近似中位數(shù)
現(xiàn)在給你這顆樹(shù)的初始權(quán)值，和修改每個(gè)點(diǎn)的代價(jià)。
再給出一個(gè)詢問(wèn)列表 \(m_1,m_2,\cdots,m_q\)，對(duì)于每個(gè)詢問(wèn)，回答使樹(shù)的近似中位數(shù)為 \(m_i\) 所需要的最小代價(jià)。
部分分
首先我們來(lái)看 \(n,q\leq1000\) 的部分。
定義函數(shù)
定義dp數(shù)組
轉(zhuǎn)移方程
其中 \(\text{cost}(k)\) 代表將 \(a_u\) 修改為 小于/等于/大于 \(m_i\) 的代價(jià)
具體地，
vector<int> cost = {c[u], c[u], c[u]};
cost[f[u]] = 0;
dp代碼實(shí)現(xiàn)：
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define med(a, b, c) (a ^ b ^ c ^ min({a, b, c}) ^ max({a, b, c}))
#define p(m, x) (x < m ? 0 : x == m ? 1 : 2)
#define ls u << 1
#define rs u << 1 | 1
const int N = 2e5 + 5, M = 4e5 + 5;
const int INF = 1e18;
int n, q;
vector<int> a(N), c(N);
vector<int> ans(M);
vector<int> f(N); // f[i]=p(m,i)
int dp[M][3];
// 更新使節(jié)點(diǎn)u的近似中位數(shù)為m的最小代價(jià)
void update(int u)
{
// 將 a[u] 修改為一個(gè) <m =m >m 的數(shù)的代價(jià)
vector<int> cost = {c[u], c[u], c[u]};
cost[f[u]] = 0;
if (rs >= n) { // 葉子結(jié)點(diǎn)
for (int i = 1; i <= 3; ++i) dp[u][i] = cost[i];
return ;
}
dp[u][0] = dp[u][1] = dp[u][2] = INF;
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
for (int k = 0; k < 3; ++k) {
int mod = med(i, j, k);
dp[u][mod] = min(dp[u][mod], dp[ls][i] + dp[rs][j] + cost[k]);
}
}
}
}
對(duì)于每個(gè)詢問(wèn)，我們都
for (int i = 1; i <= q; ++i) {
int m;
cin >> m;
for (int j = n; j; --j) {
f[j] = p(m, a[j]);
update(j);
}
cout << dp[1][1] << '\n';
}
注意這里查看 f[j] 的修改情況時(shí)一定要倒序！！！這樣才能保證從葉子節(jié)點(diǎn)開(kāi)始修改，否則你先把父親更新了結(jié)果兒子還沒(méi)更等于沒(méi)更，包WA的。
部分分優(yōu)化（滿分）
我們注意到，可以把問(wèn)詢離線下來(lái)。
把問(wèn)詢從小到大排序后，我們?cè)倏瓷洗a，可以發(fā)現(xiàn)每次增大詢問(wèn)值后，并不是所有的 \(f[j]\) 都需要修改。
又因?yàn)橹挥?\(f[j]\) 修改才會(huì)造成 dp 改變，只需要每輪查看哪些 \(f[j]\) 被修改了，針對(duì)它們更新從這個(gè)節(jié)點(diǎn)j不斷往上更新父親的 dp，因?yàn)轱@然除了父親這個(gè)節(jié)點(diǎn)無(wú)法更改任何其他 dp。
顯然 f[j] 是越修越大的，因此最多修改2次(0->1,1->2)。
那么，現(xiàn)在我們只需尋找一種高效的方式，每次精準(zhǔn)查找需要修改的 \(f[j]\)，顯然不能遍歷，否則直接給你炸成 Time Limit Enough
這個(gè)時(shí)候，我們想到，可以開(kāi)一個(gè) \(pos[val]\)，記錄值為 \(a_u=val\) 的 下標(biāo) \(u\)，每次問(wèn)詢值為 \(m\) 時(shí)，就遍歷 \(pos[m]\)，將其中所有 \(f[j]\) 修改為 \(1\)，注意一定要將 \(pos[m]\) 逆序，使其中內(nèi)容從 單調(diào)遞增變?yōu)?strong>單調(diào)遞減.然后更新dp。更完后，下一個(gè) \(m\) 肯定比現(xiàn)在大，因此我們可以預(yù)測(cè)這些點(diǎn)下一輪的 \(f[j]\) 必定為 \(2\) ，所以可以在現(xiàn)在這個(gè)循環(huán)提前修改。
代碼實(shí)現(xiàn)：
void modify(int u, int state) // 要修的 f[u] 和修成的值
{
f[u] = state;
while (u) {
update(u);
u >>= 1;
}
}
int main()
{
// existing code...
// 離散化
for (int i = 1; i <= n; ++i) {
pos[a[i]].push_back(i);
}
for (auto x: query) { // 處理問(wèn)詢，query為排序+離散化后問(wèn)詢數(shù)組
reverse(pos[x].begin(), pos[x].end());
for (auto i: pos[x]) modify(i, 1);
ans[x] = dp[1][1];
for (auto i: pos[x]) modify(i, 2);
}
for (int i = 1; i <= q; ++i) {
cout << ans[m[i]] << '\n';
}
AC 代碼
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ls u << 1
#define rs u << 1 | 1
const int N = 2e5 + 5, M = 4e5 + 5;
const int INF = 1e18;
int med(int a, int b, int c) { return a ^ b ^ c ^ min({a, b, c}) ^ max({a, b, c}); }
int p(int m, int x) { return m < x ? 0 : m == x ? 1 : 2; }
int n, q;
vector<int> a(N), c(N);
vector<int> ans(M);
vector<int> f(M); // f[i]=p(m,i)
int dp[M][3];
// 更新使節(jié)點(diǎn)u的近似中位數(shù)為m的最小代價(jià)
void update(int u)
{
// 將 a[u] 修改為一個(gè) <m =m >m 的數(shù)的代價(jià)
vector<int> cost = {c[u], c[u], c[u]};
cost[f[u]] = 0;
if (ls > n) { // 葉子結(jié)點(diǎn)
for (int i = 0; i < 3; ++i) dp[u][i] = cost[i];
return ;
}
dp[u][0] = dp[u][1] = dp[u][2] = INF;
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
for (int k = 0; k < 3; ++k) {
int mod = med(i, j, k);
dp[u][mod] = min(dp[u][mod], dp[ls][i] + dp[rs][j] + cost[k]);
}
}
}
}
// update the dp-tree's change due to
// f[u]'s change, which implies a change in cost_u[0/1/2]
void modify(int u, int state)
{
f[u] = state;
while (u) {
update(u);
u >>= 1;
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for (int i = 0; i <= n; ++i) {
for (int j = 0; j < 3; ++j) {
dp[i][j] = INF;
}
}
vector<int> all;
for (int i = 1; i <= n; ++i) {
cin >> a[i] >> c[i];
all.push_back(a[i]);
}
cin >> q;
vector<int> m(q + 1);
for (int i = 1; i <= q; ++i) {
cin >> m[i];
all.push_back(m[i]);
}
// printf("a: ");
// for (int i = 1; i <= n; ++i) printf("%lld ", a[i]);
// printf("\n");
// printf("m: ");
// for (int i = 1; i <= q; ++i) printf("%lld ", m[i]);
// printf("\n");
// 離散化
sort(all.begin(), all.end());
all.erase(unique(all.begin(), all.end()), all.end());
int cnt = 1;
map<int, int> corr;
for (auto i: all) {
corr[i] = cnt++;
}
map<int, vector<int>> pos;
for (int i = 1; i <= n; ++i) {
a[i] = corr[a[i]];
pos[a[i]].push_back(i);
}
for (int i = 1; i <= q; ++i) {
m[i] = corr[m[i]];
}
// printf("a: ");
// for (int i = 1; i <= n; ++i) printf("%lld ", a[i]);
// printf("\n");
// printf("m: ");
// for (int i = 1; i <= q; ++i) printf("%lld ", m[i]);
// printf("\n");
vector<int> query;
for (int i = 1; i <= q; ++i) {
query.push_back(m[i]);
}
sort(query.begin(), query.end());
query.erase(unique(query.begin(), query.end()), query.end());
// initialize dp to all '>'s
for (int i = n; i > 0; --i) {
// modify(i, 0); unnecessary cuz it's alr all 0s
update(i);
}
// for (int i = 1; i < cnt; ++i) {
// printf("dp[%lld]: {%lld, %lld, %lld}\n", i, dp[i][0], dp[i][1], dp[i][2]);
// }
for (int x = 1; x < cnt; ++x) {
reverse(pos[x].begin(), pos[x].end());
for (auto i: pos[x]) {
modify(i, 1);
}
ans[x] = dp[1][1];
for (auto i: pos[x]) {
modify(i, 2);
}
// for (int i = 1; i < cnt; ++i) {
// printf("dp[%lld]: {%lld, %lld, %lld}\n", i, dp[i][0], dp[i][1], dp[i][2]);
// }
}
for (int i = 1; i <= q; ++i) {
cout << ans[m[i]] << '\n';
}
return 0;
}
進(jìn)食后人
在執(zhí)行修改dp操作時(shí)，要把 \(a\) 和 \(m\) 所有元素都遍歷到，確保大小關(guān)系的正確性，防止有數(shù)值未更新。
這點(diǎn)尤其坑，因?yàn)槿绻阒槐闅v \(m\) 的話，樣例是 可以過(guò) 的，并且總共能 A掉 \(3\)個(gè)點(diǎn)，喜提\(16\text{pts}\)。
一定要初始化問(wèn)詢?yōu)?。
不僅如此，這個(gè)初始化必須逆序。（我卡了大概10min吧
浙公網(wǎng)安備 33010602011771號(hào)