bzoj – 4003 城池攻佔 【可並堆 lazy標記】 好題!!!

NO IMAGE

傳送門
題目大意:

小銘銘最近獲得了一副新的桌遊,遊戲中需要用 m 個騎士攻佔 n 個城池。
這 n 個城池用 1 到 n 的整數表示。除 1 號城池外,城池 i 會受到另一座城池 fi 的管轄,
其中 fi < i。也就是說,所有城池構成了一棵有根樹。這 m 個騎士用 1 到 m 的整數表示,其
中第 i 個騎士的初始戰鬥力為 si,第一個攻擊的城池為 ci。
每個城池有一個防禦值 hi,如果一個騎士的戰鬥力大於等於城池的生命值,那麼騎士就可
以佔領這座城池;否則佔領失敗,騎士將在這座城池犧牲。佔領一個城池以後,騎士的戰鬥力
將發生變化,然後繼續攻擊管轄這座城池的城池,直到佔領 1 號城池,或犧牲為止。
除 1 號城池外,每個城池 i 會給出一個戰鬥力變化引數 ai;vi。若 ai =0,攻佔城池 i 以後騎士戰鬥力會增加 vi;若 ai =1,攻佔城池 i 以後,戰鬥力會乘以 vi。注意每個騎士是單獨計算的。也就是說一個騎士攻擊一座城池,不管結果如何,均不會影響其他騎士攻擊這座城池的結果.
現在的問題是, 對於每個城池, 輸出有多少個騎士在這裡犧牲; 對於每個騎士, 輸出他攻佔的城池數量

這道題算是可並堆中最難的一道了把.. 注意左偏樹也是一顆二叉樹, 所以是滿足標記下推的, 所以對於乘的和加的打上相應的標記即可, 然後即使下放的時候有兩個, 一個是當前點要被刪除時需要提前下推一下, 而是進行合併的時候要在左右兒子有新編號的時候下推一下. 還有注意的點就是乘和加標記的先後順序關係, 線段樹中的雙標記下推規則就不細說了. 這裡的root不能初始化為自己, 因為這個跟自己沒有任何關係, 所以root[i] == 0 的就不用進行判斷了.. 細節請看程式碼

AC Code

const int maxn = 3e5   5;
int root[maxn];
struct Ltree {
int ls[maxn<<1], rs[maxn<<1]; // 左右兒子的編號
ll val[maxn<<1], mul[maxn<<1], add[maxn<<1];
// 該點的值, 改點的 /*的標記, 因為左偏樹也是二叉樹
// 所以可以想線段樹那樣進行下放
void funmul(int id, ll tmp) {
val[id] *= tmp; mul[id] *= tmp;
add[id] *= tmp;
}
void funadd(int id, ll tmp) {
val[id]  = tmp; add[id]  = tmp;
}
void pushdown(int id) {
if (mul[id] != 1) {
funmul(ls[id], mul[id]);
funmul(rs[id], mul[id]);
mul[id] = 1;
}
if (add[id]) {
funadd(ls[id], add[id]);
funadd(rs[id], add[id]);
add[id] = 0;
}
}
int Un(int x, int y){  // 小根堆/ 看情況維護, 改個符號就行
if (!x || !y) return x y;
if (val[x] > val[y]) swap(x,y);
pushdown(x);
rs[x] = Un(rs[x], y);
swap(ls[x], rs[x]);
return x;
}
void pop(int &x) {
x = Un(ls[x], rs[x]);
}
int top(int x) {
return val[x];
}
}heap;
int a[maxn];
ll h[maxn], v[maxn], ci[maxn];
int ans[maxn], siz[maxn], dep[maxn];
int n, m;
struct node {
int to, next, w;
}e[maxn];
int cnt, head[maxn];
void init() {
cnt = 0; Fill(head, -1);
}
void add(int u, int v, int w) {
e[cnt] = node{v, head[u], w};
head[u] = cnt  ;
}
void dfs(int u, int fa, int d) {
dep[u] = d   1;
for (int i = head[u] ; ~i ; i = e[i].next) {
int to = e[i].to;
dfs(to, u, d   1);
root[u] = heap.Un(root[u], root[to]);
}
if (!root[u]) return ;
int rf = root[u];
while (heap.val[rf] < h[u]) {
heap.pushdown(rf);
siz[u];
ans[rf] = dep[ci[rf]] - dep[u];
heap.pop(root[u]);
if (!root[u]) return ;
rf = root[u];
}
if (a[u]) heap.funmul(rf, v[u]);
else heap.funadd(rf, v[u]);
}
void solve() {
scanf("%d%d", &n, &m); init();
for (int i = 1 ; i <= n ; i   ) scanf("%lld", h i);
for (int i = 2 ; i <= n ; i   ) {
int x;
scanf("%d%d%lld", &x, &a[i], &v[i]);
add(x, i, 1);
}
for (int i = 1 ; i <= m ; i   ) {
ll x;
scanf("%lld%d", &x, ci i);
heap.val[i] = x; heap.mul[i] = 1;
root[ci[i]] = heap.Un(root[ci[i]], i);
}
Fill(ans, -1); dfs(1, -1, 0);
for (int i = 1; i <= n ; i   ) printf("%d\n", siz[i]);
for (int i = 1; i <= m ; i   ) {
printf("%d\n", ans[i] == -1 ? dep[ci[i]]: ans[i]);
}
}