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

AC Code

``````const int maxn = 3e5   5;
int root[maxn];
struct Ltree {
int ls[maxn<<1], rs[maxn<<1]; // 左右兒子的編號
// 該點的值, 改點的 /*的標記, 因為左偏樹也是二叉樹
// 所以可以想線段樹那樣進行下放
void funmul(int id, ll tmp) {
val[id] *= tmp; mul[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;
}
}
}
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];
void init() {
}
void add(int u, int v, int w) {
}
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]);
}
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]);