「JLOI2015」城池攻占 - 可并堆/三进制倍增 | Bill Yang's Blog

「JLOI2015」城池攻占 - 可并堆/三进制倍增

题目大意

    小铭铭最近获得了一副新的桌游,游戏中需要用$m$个骑士攻占$n$个城池。
    这$n$个城池用$1$到$n$的整数表示。除$1$号城池外,城池$i$会受到另一座城池$f_i$的管辖,其中$f_i\lt i$。也就是说,所有城池构成了一棵有根树。这$m$个骑士用$1$到$m$的整数表示,其中第$i$个骑士的初始战斗力为$s_i$,第一个攻击的城池为$c_i$。
    每个城池有一个防御值$h_i$,如果一个骑士的战斗力大于等于城池的生命值,那么骑士就可以占领这座城池;否则占领失败,骑士将在这座城池牺牲。占领一个城池以后,骑士的战斗力将发生变化,然后继续攻击管辖这座城池的城池,直到占领$1$号城池,或牺牲为止。
    除$1$号城池外,每个城池$i$会给出一个战斗力变化参数$a_i,v_i$。若$a_i=0$,攻占城池$i$以后骑士战斗力会增加$v_i$;若$a_i=1$,攻占城池$i$以后,战斗力会乘以$v_i$。注意每个骑士是单独计算的。也就是说一个骑士攻击一座城池,不管结果如何,均不会影响其他骑士攻击这座城池的结果。
现在的问题是,对于每个城池,输出有多少个骑士在这里牺牲;对于每个骑士,输出他攻占的城池数量。


题目分析

本题有个很简单的倍增思想,见大佬博客

我们可以考虑暴力。
每个点$i$维护一个集合$S_i$表示可以到达$i$的所有骑士以及它们的战斗力。
在$i$结点去掉所有战斗力不够的骑士,然后将当前的$S_i$与$S_{f_i}$合并。

这样我们需要一个支持合并,有序的(方便删除),可以给集合全部加、乘一个数的数据结构。
可以使用带标记的可并堆。给堆顶打上标记,每次要用到可并堆元素值时标记下传。


代码

要爆栈。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
typedef long long LL;
inline const LL Get_Int() {
LL num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=300005;
struct Tree {
int l,r,dist;
LL val,mul,add;
Tree(LL x=0):l(0),r(0),dist(0),val(x),mul(1),add(0) {}
} tree[maxn];
struct LeftSideTree {
int n;
#define ls tree[index].l
#define rs tree[index].r
#define a(x) tree[x].val
#define dist(x) tree[x].dist
int merge(int x,int y) {
if(!x||!y)return x+y;
if(a(x)>a(y))swap(x,y);
push_down(x);
tree[x].r=merge(tree[x].r,y);
if(dist(tree[x].r)>dist(tree[x].l))swap(tree[x].l,tree[x].r);
if(!tree[x].r)dist(x)=0;
else dist(x)=dist(tree[x].r)+1;
return x;
}
void update(int index,LL mul,LL add) {
if(!index||(mul==1&&add==0))return;
a(index)=a(index)*mul+add;
tree[index].add=tree[index].add*mul+add;
tree[index].mul*=mul;
}
void push_down(int index) {
update(ls,tree[index].mul,tree[index].add);
update(rs,tree[index].mul,tree[index].add);
tree[index].mul=1,tree[index].add=0;
}
int pop(int index) {
push_down(index);
int tmp=merge(ls,rs);
ls=rs=0;
return tmp;
}
} heap;
LL a[maxn],v[maxn],Defend[maxn];
int n,m,from[maxn],Death[maxn],Die[maxn],Depth[maxn],root[maxn];
vector<int>edges[maxn];
void AddEdge(int x,int y) {
edges[x].push_back(y);
}
void Dfs(int Now,int depth) {
Depth[Now]=depth;
for(int Next:edges[Now]) {
Dfs(Next,depth+1);
root[Now]=heap.merge(root[Now],root[Next]);
}
while(root[Now]&&tree[root[Now]].val<Defend[Now]) {
Death[Now]++;
Die[root[Now]]=Now;
root[Now]=heap.pop(root[Now]);
}
if(a[Now])heap.update(root[Now],v[Now],0);
else heap.update(root[Now],1,v[Now]);
}
int main() {
int size=60<<20;
__asm__ ("movq %0,%%rsp\n"::"r"((char*)malloc(size)+size));
n=Get_Int();
m=Get_Int();
for(int i=1; i<=n; i++)Defend[i]=Get_Int();
for(int i=2; i<=n; i++) {
int x=Get_Int();
AddEdge(x,i);
a[i]=Get_Int();
v[i]=Get_Int();
}
for(int i=1; i<=m; i++) {
tree[i]=Tree(Get_Int());
from[i]=Get_Int();
root[from[i]]=heap.merge(root[from[i]],i);
}
Dfs(1,1);
for(int i=1; i<=n; i++)printf("%d\n",Death[i]);
for(int i=1; i<=m; i++)printf("%d\n",Depth[from[i]]-Depth[Die[i]]);
exit(0);
}

本篇文章有用吗?有用还不快点击!
0%