【CZYZ2009暑假集训提高组6】魔兽争霸

来源和评测点

CZYZ2009暑假集训提高组6

题目

【题目大意】
小 x 正在销魂地玩魔兽
他正控制着死亡骑士和 n个食尸鬼(编号 1~n)去打猎

死亡骑士有个魔法,叫做“死亡缠绕” ,可以给食尸鬼补充 HP
战斗过程中敌人会对食尸鬼实施攻击,食尸鬼的 HP 会减少

小 x 希望随时知道自己部队的情况, 即 HP 值第 k 多的食尸鬼有多少 HP, 以
便决定如何施放魔法
请同学们帮助他:)

小 x 向你发出 3种信号: (下划线在输入数据中表现为空格)

A_i_a 表示敌军向第 i 个食尸鬼发出了攻击,
并使第 i 个食尸鬼损失了 a 点 HP,如果它的 HP<=0,
那么这个食尸鬼就死了(Undead 也是要死的„„)。
敌军不会攻击一个已死的食尸鬼。

C_i_a 表示死亡骑士向第i 个食尸鬼放出了死亡缠绕,
并使其增加了a点HP。 HP 值没有上限。
死亡骑士不会向一个已死的食尸鬼发出死亡缠绕

Q_k 表示小 x 向你发出询问
【输入格式】
第一行,一个正整数 n
以后 n个整数 表示 n个食尸鬼的初始 HP 值
接着一个正整数 m
以下 m行 每行一个小 x 发出的信号
40%的数据 n<=3000 m<=5000
70%的数据 n<=8000 m<=10000
100%的数据 n<=30000 m<=50000
90%的数据随机生成
食尸鬼 HP 没有上限
数据保证任意时刻食尸鬼的 HP 值在 longint范围内
数据保证 A 和 C 命令中的食尸鬼是活着的
输入数据中没有多余空格、换行
【输出格式】
对于小 x 的每个询问, 输出 HP 第 k 多的食尸鬼有多少 HP,
如果食尸鬼总数不足 k 个,输出-1。每个一行数。
最后一行输出一个数:战斗结束后剩余的食尸鬼数
【输入样例】
5
1 2 3
4 5
10
Q 2
A 4 6
C 1 4
Q 2
A 2 1
A 3 3
A 1 3
Q 4
C 2 10
Q 1
【输出样例】
4
5
-1
11
3

分析

这道题还是挺有趣的
利用了Splay的灵活性
当时是比赛吧,写了200+行感觉思路完全是错的
因为节点编号会换,差点心态爆炸想放弃
冷静一想,毕竟是人发明的东西,那就可以改造
我是用了一个数组存储对应的真实编号
(后来看别人的代码,其实存着每个HP就好了……)

难度并不算太大,就不讲什么了,看代码吧

代码

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
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=80000;
int hh[MAXN+10];
//**********************************************
struct pt
{
int son[2],f;
int d,c,n;
pt()
{
son[0]=son[1]=-1;
f=0;
d=0;
c=n=1;
}
}p[MAXN+10];
//**********************************************
void update(int x)
{
p[x].c=p[x].n;
int lc=p[x].son[0],rc=p[x].son[1];
if(lc>0) p[x].c+=p[lc].c;
if(rc>0) p[x].c+=p[rc].c;
}
void rotate(int x,int w)
{
int f=p[x].f,ff=p[f].f;
int xson=p[x].son[w];
if(xson>0) p[xson].f=f;
p[f].son[1-w]=xson;
if(p[ff].son[0]==f) p[ff].son[0]=x;
else if(p[ff].son[1]==f) p[ff].son[1]=x;
p[x].f=ff;
p[x].son[w]=f;
p[f].f=x;
update(f);
update(x);
}
int root;
void splay(int x,int rt)
{
while(p[x].f!=rt)
{
int f=p[x].f,ff=p[f].f;
if(ff==rt)
{
if(p[f].son[0]==x) rotate(x,1);
else if(p[f].son[1]==x) rotate(x,0);
}
else
{
if(p[ff].son[0]==f and p[f].son[0]==x) rotate(f,1),rotate(x,1);
else if(p[ff].son[0]==f and p[f].son[1]==x) rotate(x,0),rotate(x,1);
else if(p[ff].son[1]==f and p[f].son[0]==x) rotate(x,1),rotate(x,0);
else if(p[ff].son[1]==f and p[f].son[1]==x) rotate(f,0),rotate(x,0);
}
}
if(rt==0) root=x;
}
int findip(int d)
{
int x=root;
while(p[x].d!=d)
{
if(d>p[x].d)
{
int lc=p[x].son[0];
if(lc<0) return x;
x=lc;
}
else
{
int rc=p[x].son[1];
if(rc<0) return x;
x=rc;
}
}
return x;
}
int len;
void add(int f,int d)
{
len++;p[len].f=f;
p[len].son[0]=p[len].son[1]=-1;
p[len].c=p[len].n=1;p[len].d=d;
if(d>p[f].d) p[f].son[0]=len;
else p[f].son[1]=len;
}
void addnum(int hk,int d)
{
if(root==0)
{
root=++len;p[len].f=0;
p[len].son[0]=p[len].son[1]=-1;
p[len].c=p[len].n=1;p[len].d=d;
hh[hk]=len;//
}
else
{
int x=findip(d);
if(p[x].d==d)
{
p[x].n++;
update(x);
hh[hk]=x;//
}
else
{
add(x,d);
update(x);
hh[hk]=len;//
}
splay(x,0);
}
}
void del(int d)
{
int x=findip(d);
if(p[x].n>1)
{
p[x].n--;
update(x);
splay(x,0);
}
else
{
splay(x,0);
if(p[x].son[0]==-1 and p[x].son[1]==-1)
{
len=0;root=0;
}
else if(p[x].son[0]>0 and p[x].son[1]==-1)
{
root=p[x].son[0];
p[root].f=0;
}
else if(p[x].son[0]==-1 and p[x].son[1]>0)
{
root=p[x].son[1];
p[root].f=0;
}
else
{
int k=p[x].son[0];
while(p[k].son[1]>0) k=p[k].son[1];
p[k].son[1]=p[x].son[1];
p[p[x].son[0]].f=0;
p[p[x].son[1]].f=k;
update(k);splay(k,0);
}
}
}
//**********************************************
int asknum(int k)
{
int x=root;
if(k>p[x].c) return -1;
while(x>0)
{
int lc=p[x].son[0];
int lcc=lc>0?p[lc].c:0;
if(k<=lcc) x=lc;
else if(k>lcc+p[x].n) k-=lcc+p[x].n,x=p[x].son[1];
else
{
splay(x,0);
return p[x].d;
}
}
return -2;
}
void solve1(int k,int a)//-
{
int d=p[ hh[k] ].d;
del(d);
if(d-a>0) addnum(k,d-a);
}
void solve2(int k,int a)//+
{
int d=p[ hh[k] ].d;
del(d);
addnum(k,d+a);
}
//**********************************************
char s[10];
int main()
{
len=0;root=0;
int n;scanf("%d",&n);
for(int i=1;i<=n;i++)
{
int t;
scanf("%d",&t);
addnum(i,t);
}
int m;scanf("%d",&m);
while(m--)
{
int a;scanf("%s%d",s,&a);
if(s[0]=='Q') printf("%d\n",asknum(a));
else
{
int b;scanf("%d",&b);
if(s[0]=='A') solve1(a,b);
else solve2(a,b);
}
}
printf("%d",p[root].c);
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/2018-01/魔兽争霸.html
转载请注明出处,谢谢!

给我投食吧,您的支持将鼓励我继续创作!