【左偏樹】【P3261】 [JLOI2015]城池攻占

Description

小銘銘最近獲得了一副新的桌游，游戲中需要用 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。注意每個騎士是單獨計算的。也就是說一個騎士攻擊一座城池，不管結果如何，均不會影響其他騎士攻擊這座城池的結果。如果 \(a_i~=~1\)，保證 \(v_i~>~0\)

現在的問題是，對于每個城池，輸出有多少個騎士在這里犧牲；對于每個騎士，輸出他攻占的城池數量。

Limitation

\(1~\leq~n,~m~\leq~3~\times~10^5\)

Solution

最近沉迷頹廢學習很久沒寫博客了啊QAQ

考慮由于若在一個位置的戰斗力是乘法則只會乘正整數，當同一個節點的騎士向上攻占的時候，他們相互之間戰斗力的大小關系是不變的。如果我們維護每個節點上還剩下了多少騎士，那么每到一個節點所有小于某個值的元素都要被刪除，這提示我們使用堆來維護。由于需要支持信息的合并，我們考慮使用左偏樹來完成。

考慮到達一個節點以后會給節點里所有的元素做一次修改，但是這個修改是不影響堆的結構的，于是可以在堆的根節點上打標記，不斷下方即可。

Code

#include <cstdio>
#include <vector>
#include <algorithm>
#ifdef ONLINE_JUDGE
#define freopen(a, b, c)
#endiftypedef long long ll;namespace IPT {const int L = 1000000;char buf[L], *front=buf, *end=buf;char GetChar() {if (front == end) {end = buf + fread(front = buf, 1, L, stdin);if (front == end) return -1;}return *(front++);}
}template <typename T>
inline void qr(T &x) {char ch = IPT::GetChar(), lst = ' ';while ((ch > '9') || (ch < '0')) lst = ch, ch=IPT::GetChar();while ((ch >= '0') && (ch <= '9')) x = (x << 1) + (x << 3) + (ch ^ 48), ch = IPT::GetChar();if (lst == '-') x = -x;
}namespace OPT {char buf[120];
}template <typename T>
inline void qw(T x, const char aft, const bool pt) {if (x < 0) {x = -x, putchar('-');}int top=0;do {OPT::buf[++top] = static_cast<char>(x % 10 + '0');} while (x /= 10);while (top) putchar(OPT::buf[top--]);if (pt) putchar(aft);
}const int maxn = 300010;struct Kni {ll s;int c, ans;
};
Kni kt[maxn];struct Tree {Kni* v;ll addv, addm, dist;Tree *ls, *rs;Tree(Kni *_v = NULL) {ls = rs = NULL;dist = addv = 0; addm = 1;v = _v;}inline void addtag(ll x) {this->addv += x;this->v->s += x;}inline void multag(ll x) {this->addm *= x;this->addv *= x;this->v->s *= x;}inline void pd(ll x, ll y) {this->multag(y); this->addtag(x); }inline void pushdown() {if (this->ls) this->ls->pd(this->addv, this->addm);if (this->rs) this->rs->pd(this->addv, this->addm);this->addv = 0; this->addm = 1;}inline void pushup() {this->dist = (this->rs ? this->rs->dist : 0) + 1;}
};
Tree *tree[maxn];int n, m;
int fa[maxn], depth[maxn], died[maxn];
ll MU[maxn], a[maxn], v[maxn]; 
std::vector<int>son[maxn], kts[maxn];void dfs(int);
Tree *merge(Tree*, Tree*);int main() {freopen("1.in", "r", stdin);qr(n); qr(m);for (int i = 1; i <= n; ++i) qr(MU[i]);for (int i = 2; i <= n; ++i) {qr(fa[i]); son[fa[i]].push_back(i); qr(a[i]); qr(v[i]);}for (int i = 1; i <= m; ++i) {qr(kt[i].s); qr(kt[i].c); kt[i].ans = -1;kts[kt[i].c].push_back(i);}dfs(1);for (int i = 1; i <= n; ++i) qw(died[i], '\n', true);for (int i = 1; i <= m; ++i) qw(~kt[i].ans ? kt[i].ans : depth[kt[i].c], '\n', true);return 0;
}Tree *merge(Tree *u, Tree *v) {if (!u) return v;if (!v) return u;u->pushdown(); v->pushdown();if (u->v->s > v->v->s) std::swap(u, v);u->rs = merge(u->rs, v);if ((u->rs) && ((!u->ls) || (u->rs->dist > u->ls->dist))) std::swap(u->ls, u->rs);u->pushup();return u;
}void dfs(int u) {depth[u] = depth[fa[u]] + 1;for (auto to : son[u]) {dfs(to);while (tree[to] && (tree[to]->v->s < MU[u])) {++died[u];tree[to]->v->ans = depth[tree[to]->v->c] - depth[u];tree[to]->pushdown();tree[to] = merge(tree[to]->ls, tree[to]->rs);}tree[u] = merge(tree[u], tree[to]);}for (auto i : kts[u]) {if (kt[i].s >= MU[u]) tree[u] = merge(tree[u], new Tree(&kt[i]));else {++died[u];kt[i].ans = 0;}}if (!tree[u]) return;if (a[u]) tree[u]->multag(v[u]);else tree[u]->addtag(v[u]);
}

Summary

只要信息修改后不影響堆的形態，可以在左偏樹上打標記來完成修改。