左偏树
BB
此时，一个菜逼路过 QAQ
Introduction
左偏树，顾名思义，就是一棵向左偏的树（大雾
左偏树，属于可并堆的一种，可以在O(logn)时间内完成插入、删除节点、合并堆等操作
- 左偏树 - OI WIKI
https://oi-wiki.org/ds/leftist-tree/
Monkey King - luogu P1456
Description
一开始有n只孤独的猴子，然后他们要打m次架，每次打架呢，都会拉上自己朋友最牛叉的出来跟别人打，打完之后战斗力就会减半，每次打完架就会成为朋友（正所谓不打不相识o(∩_∩)o ）。问每次打完架之后那俩猴子最牛叉的朋友战斗力还有多少，若朋友打架就输出-1.
范围：n, m <= 100000，可能存在多组输入
Sample Input
5
20
16
10
10
4
5
2 3
3 4
3 5
4 5
1 5
Sample Output
8
5
5
-1
10
Solution
接近裸的左偏树
“战力减半”需要先把节点删除，再插入
#include <bits/stdc++.h>
using namespace std;
const int N = 100000 + 15;
int ch[N][2], val[N], d[N], ft[N];
inline void init(int n) {
for(int i = 1; i <= n; i++) {
ft[i] = i;
d[i] = 1;
ch[i][0] = ch[i][1] = 0;
}
}
inline int find(int x) {
return ft[x] == x ? x : ft[x] = find(ft[x]);
}
inline int merge(int x, int y) {
if(!x || !y) {
return x | y;
}
if(val[x] < val[y]) {
swap(x, y);
}
ch[x][1] = merge(ch[x][1], y);
if(d[ch[x][0]] < d[ch[x][1]]) {
swap(ch[x][0], ch[x][1]);
}
d[x] = d[ch[x][1]] + 1;
return x;
}
int main() {
int n, m;
while(~scanf("%d", &n)) {
init(n);
for(int i = 1; i <= n; i++) {
scanf("%d", &val[i]);
}
scanf("%d", &m);
while(m--) {
int u, v;
scanf("%d%d", &u, &v);
u = find(u), v = find(v);
if(u == v) {
puts("-1");
} else {
for(int k = 0; k < 2; k++) {
val[u] >>= 1;
int x = merge(ch[u][0], ch[u][1]);
ch[u][0] = ch[u][1] = 0;
int y = merge(u, x);
ft[u] = ft[x] = y;
swap(u, v);
}
u = find(u), v = find(v);
int x = merge(u, v);
ft[u] = ft[v] = x;
printf("%d\n", val[x]);
}
}
}
}
[APIO2012]派遣 - luogu P1552
Description
在这个帮派里，有一名忍者被称之为Master。除了Master以外，每名忍者都有且仅有一个上级。为保密，同时增强忍者们的领导力，所有与他们工作相关的指令总是由上级发送给他的直接下属，而不允许通过其他的方式发送。
现在你要招募一批忍者，并把它们派遣给顾客。你需要为每个被派遣的忍者支付一定的薪水，同时使得支付的薪水总额不超过你的预算。另外，为了发送指令，你需要选择一名忍者作为管理者，要求这个管理者可以向所有被派遣的忍者发送指令，在发送指令时，任何忍者（不管是否被派遣）都可以作为消息的传递人。管理者自己可以被派遣，也可以不被派遣。当然，如果管理者没有被排遣，你就不需要支付管理者的薪水。
你的目标是在预算内使顾客的满意度最大。这里定义顾客的满意度为派遣的忍者总数乘以管理者的领导力水平，其中每个忍者的领导力水平也是一定的。
写一个程序，给定每一个忍者i的上级Bi，薪水Ci，领导力Li，以及支付给忍者们的薪水总预算M，输出在预算内满足上述要求时顾客满意度的最大值。
范围：
1 ≤ N ≤ 100,000 忍者的个数；
1 ≤ M ≤ 1,000,000,000 薪水总预算；
0 ≤ Bi < i 忍者的上级的编号；
1 ≤ Ci ≤ M 忍者的薪水；
1 ≤ Li ≤ 1,000,000,000 忍者的领导力水平。
Sample Input
5 4
0 3 3
1 3 5
2 2 2
1 2 4
2 3 1
Sample Output
6
Solution 1 - 左偏树
不难想到就是枚举子树，对于每一棵子树，贪心的选小的元素，这样才能使得数量最多
因此，维护大根堆，使得队内元素和不超过M，合并时，如果超过M，就不断把根pop掉
由于每个元素只可能入堆一次，故总复杂度为O(nlogn)
另外，维护和和维护数量这一工作，推荐放在并查集上跑
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100000 + 15;
int ch[N][2], d[N], val[N], ft[N];
int cnt[N], lzy[N];
ll sum[N];
vector<int> graph[N];
int l[N];
inline void init() {
for(int i = 1; i < N; i++) {
ft[i] = i;
d[i] = 1;
cnt[i] = 1;
}
}
inline int find(int x) {
return ft[x] == x ? x : ft[x] = find(ft[x]);
}
inline int merge(int x, int y) {
if(!x || !y) {
return x | y;
}
if(val[x] < val[y]) {
swap(x, y);
}
ch[x][1] = merge(ch[x][1], y);
if(d[ch[x][0]] < d[ch[x][1]]) {
swap(ch[x][0], ch[x][1]);
}
d[x] = d[ch[x][1]] + 1;
return x;
}
ll solve(int u, int k) {
ll ans = 0;
int rt = u;
for(int v : graph[u]) {
ans = max(ans, solve(v, k));
int x = find(v);
int nrt = merge(rt, x);
sum[nrt] = sum[x] + sum[rt];
cnt[nrt] = cnt[x] + cnt[rt];
ft[x] = ft[rt] = ft[nrt] = nrt;
rt = nrt;
}
// Pop
//printf("? %lld\n", sum[rt]);
while(sum[rt] > k) {
int ls = ch[rt][0], rs = ch[rt][1];
int y = merge(ls, rs);
sum[y] = sum[rt] - val[rt];
cnt[y] = cnt[rt] - 1;
ft[y] = ft[rt] = y;
ch[rt][0] = ch[rt][1] = 0;
rt = y;
}
//printf("? %d %d %d\n", rt, cnt[rt], l[u]);
ans = max(ans, 1LL * cnt[rt] * l[u]);
return ans;
}
int main() {
init();
int n, k;
scanf("%d%d", &n, &k);
for(int i = 1; i <= n; i++) {
int p;
scanf("%d%d%d", &p, &val[i], &l[i]);
sum[i] = val[i];
if(p) {
graph[p].push_back(i);
}
}
ll ans = solve(1, k);
printf("%lld\n", ans);
}
Solution 2 - set启发式合并（非正解！）
其实暴力也是可以的，set启发式合并总复杂度O(nlog^2n)
会TLE一个点，开O2可以全部AC
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100000 + 15;
int c[N], l[N];
int ft[N];
ll sum[N];
multiset<int, greater<int> > st[N];
vector<int> graph[N];
inline int find(int x) {
return ft[x] == x ? x : ft[x] = find(ft[x]);
}
inline void update(int x, int y, int k) {
x = find(x), y = find(y);
if(st[x].size() < st[y].size()) {
swap(x, y);
}
ft[y] = x;
for(int ele : st[y]) {
st[x].emplace(ele);
}
st[y].clear();
sum[x] += sum[y];
while(!st[x].empty() && sum[x] > k) {
multiset<int>::iterator it = st[x].begin();
sum[x] -= *it;
st[x].erase(it);
}
}
inline ll solve(int u, int k) {
ll ans = 0;
for(int v : graph[u]) {
ans = max(ans, solve(v, k));
update(u, v, k);
}
int x = find(u);
ans = max(ans, (ll)st[x].size() * l[u]);
return ans;
}
int main() {
int n, k;
scanf("%d%d", &n, &k);
for(int i = 1; i <= n; i++) {
int p;
scanf("%d%d%d", &p, &c[i], &l[i]);
ft[i] = i;
if(c[i] <= k) {
st[i].emplace(c[i]);
sum[i] = c[i];
}
if(p) {
graph[p].emplace_back(i);
}
}
ll ans = solve(1, k);
printf("%lld\n", ans);
}
「JLOI2015」城池攻占 - loj 2107
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。注意每个骑士是单独计算的。也就是说一个骑士攻击一座城池，不管结果如何，均不会影响其他骑士攻击这座城池的结果。
现在的问题是，对于每个城池，输出有多少个骑士在这里牺牲；对于每个骑士，输出他攻占的城池数量。
5 5
50 20 10 10 30
1 1 2
2 0 5
2 0 -10
1 0 10
20 2
10 3
40 4
20 4
35 5
Sample Output
2
2
0
0
0
1
1
3
1
1
Solution
可以发现可以对骑士在树上维护堆，这样DFS遍历树时，先将子树剩余的堆合并后，再将此时堆中战力小于防御值的元素弹走，同时记录此时战死在此的骑士数量，再更新堆中的元素的大小
合并堆用左偏树，弹走元素优先弹走最小所以是小根堆，更新堆中所有元素大小是同时更新的，且不会改变相对大小（题目中的操作为同时加上一个数，或者同时乘上一个 正数），所以可以用类似线段树的懒惰标记搞搞
最后需要考虑的是如何统计每个骑士攻占了几个点，由于骑士一直往上爬，所以战死的点的深度减去原深度即是答案，这在弹走时同时统计即可
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 300000 + 15;
int a[N];
ll v[N], h[N], val[N];
ll lzyAdd[N], lzyMul[N];
int dpt[N], ed[N], c[N];
int mp[N];
int ch[N][2], d[N], cnt[N];
vector<int> graph[N];
inline void init() {
for (int i = 1; i < N; i++) {
d[i] = 1;
lzyMul[i] = 1;
}
}
inline void pushDown(int x) {
if (lzyAdd[x] != 0 || lzyMul[x] != 1) {
for (int k = 0; k < 2; k++) {
val[ch[x][k]] = lzyMul[x] * val[ch[x][k]] + lzyAdd[x];
lzyMul[ch[x][k]] *= lzyMul[x];
lzyAdd[ch[x][k]] = lzyMul[x] * lzyAdd[ch[x][k]] + lzyAdd[x];
}
lzyAdd[x] = 0;
lzyMul[x] = 1;
}
}
inline int merge(int x, int y) {
if (!x || !y) {
return x | y;
}
if (val[x] > val[y]) {
swap(x, y);
}
pushDown(x);
ch[x][1] = merge(ch[x][1], y);
if (d[ch[x][0]] < d[ch[x][1]]) {
swap(ch[x][0], ch[x][1]);
}
d[x] = d[ch[x][1]] + 1;
return x;
}
inline void dfs(int u) {
int rt = mp[u];
for (int v : graph[u]) {
dpt[v] = dpt[u] + 1;
dfs(v);
rt = merge(rt, mp[v]);
}
// printf("u = %d\n", u);
while (rt && val[rt] < h[u]) {
// printf("rt = %d, val = %lld\n", rt, val[rt]);
cnt[u]++;
ed[rt] = u;
pushDown(rt);
rt = merge(ch[rt][0], ch[rt][1]);
}
// printf("rt = %d, val = %lld\n", rt, val[rt]);
mp[u] = rt;
if (a[u] == 0) {
val[rt] += v[u];
lzyAdd[rt] += v[u];
} else {
val[rt] *= v[u];
lzyMul[rt] *= v[u];
lzyAdd[rt] *= v[u];
}
}
int main() {
init();
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%lld", &h[i]);
}
for (int i = 2; i <= n; i++) {
int p;
scanf("%d%d%lld", &p, &a[i], &v[i]);
graph[p].push_back(i);
}
for (int i = 1; i <= m; i++) {
scanf("%lld%d", &val[i], &c[i]);
mp[c[i]] = merge(mp[c[i]], i);
}
dpt[1] = 1;
dfs(1);
for (int i = 1; i <= n; i++) {
printf("%d\n", cnt[i]);
}
for (int i = 1; i <= m; i++) {
printf("%d\n", dpt[c[i]] - dpt[ed[i]]);
}
}
