域名网站有哪些,wordpress ux主题,网络服务器的配置与应用心得,html网站设计源码Description 小铭铭最近获得了一副新的桌游#xff0c;游戏中需要用 m 个骑士攻占 n 个城池。这 n 个城池用 1 到 n 的整数表示。除 1 号城池外#xff0c;城池 i 会受到另一座城池 fi 的管辖#xff0c;其中 fi i。也就是说#xff0c;所有城池构成了一棵有根树。这 m…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], *frontbuf, *endbuf;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, chIPT::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 top0;do {OPT::buf[top] static_castchar(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::vectorintson[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 只要信息修改后不影响堆的形态可以在左偏树上打标记来完成修改。 转载于:https://www.cnblogs.com/yifusuyi/p/10539753.html
