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)
- #endif
- typedef 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
只要信息修改后不影响堆的形态, 可以在左偏树上打标记来完成修改.
来源: http://www.bubuko.com/infodetail-2988700.html