魔兽争霸(war.pas/cpp/c)
小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 向你发出询问
输入(war.in)
第一行，一个正整数 n ，以后n 个整数表示n 个食尸鬼的初始HP 值。
接着一个正整数m，以下m 行每行一个小x为 发出的信号。
输出(war.out)
对于小x 的每个询问，输出HP 第k 多的食尸鬼有多少HP，如果食尸鬼总数不足k 个，输出-1。每行一个数。
最后一行输出一个数：战斗结束后剩余的食尸鬼数。
样例
Input Output
5 4
1 2 3 5
4 5 -1
10 11
Q 2 3
A 4 6
C 1 4
Q 2
A 2 1
A 3 3
A 1 3
Q 4
C 2 10
Q 1
约定
40%的数据n<=3000 m<=5000
70%的数据n<=8000 m<=10000
100%的数据n<=30000 m<=50000
90%的数据随机生成。
食尸鬼HP 没有上限。
数据保证任意时刻食尸鬼的HP值在longint 范围内。
数据保证A 和C 命令中的食尸鬼是活着的。
输入数据中没有多余空格、换行。
评测数据下载：http://pan.baidu.com/share/link?shareid=432194&uk=255096381&third=15
解法：sbt。
可以用sbt解决此题，以root为根，s[i] 记录以 i 为根的树的节点数，l[i] 记录 i 号点的左儿子，y[i] 记录 i 号点的右儿子，p[i] 记录 i 号点的值。
对于A操作，①找到 a 点在树中的位置，②将a点删除，p[a]-=b，若p[a]>0--->insert(root,a)；
对于C操作，①找到 a 点在树中的位置，②将a点删除，p[a]+=b，insert(root,a)；
对于Q操作，若a>a[root]--->printf("-1\n")，否则select（root，a）；
对于A、C操作，①操作用find（int t，int k）找到k号点在树中的位置，②操作，先用get（int t，int k）找到p[k]在树中的后继节点，然后用p[k]的后继结点代替k号节点。
代码：
#include<cstdio>
#include<algorithm>
#define maxn (30000+100)
using namespace std;
int root=0,s[maxn],l[maxn],r[maxn],p[maxn];
void init()
{
freopen("war.in","r",stdin);
freopen("war.out","w",stdout);
}
inline void data(int &t,int k)
{
s[k]=s[t];
s[t]=s[l[t]]+s[r[t]]+1;
t=k;
}
inline void right_rotate(int &t)
{
int k;
k=l[t],l[t]=r[k],r[k]=t;
data(t,k);
}
inline void left_rotate(int &t)
{
int k;
k=r[t],r[t]=l[k],l[k]=t;
data(t,k);
}
void maintain(int &t,bool flag)
{
if(flag)
if(s[l[l[t]]]>s[r[t]])
right_rotate(t);
else
if(s[r[l[t]]]>s[r[t]])
left_rotate(l[t]),right_rotate(t);
else
return;
else
if(s[r[r[t]]]>s[l[t]])
left_rotate(t);
else
if(s[l[r[t]]]>s[l[t]])
right_rotate(r[t]),left_rotate(t);
else
return;
maintain(l[t],1);
maintain(r[t],0);
maintain(t,1);
maintain(t,0);
}
void insert(int &t,int k)
{
if(t==0)
{
t=k,l[t]=r[t]=0,s[t]=1;
return;
}
s[t]++;
if(p[k]<p[t])insert(l[t],k);
else insert(r[t],k);
maintain(t,p[k]<p[t]);
}
void get(int &t,int &k)
{
s[t]--;
if(s[l[t]]==0)//找到后继节点
{
int kk=r[t];
l[t]=l[k],s[t]=s[k];
r[t]=r[k]==t?r[t]:r[k];//处理t是k的儿子/非儿子的情况
s[k]=0,k=t,t=kk;
return;
}
get(l[t],k);
}
//在以t为根的树中，找到k号点，若能找到，则返回1，否则返回0
//若p[t]==p[k]，那么k号点可能在l[t]中，也可能在r[t]中，所以把find()定义为bool
//若p[k]<p[t],k一定在l[t]中；
//若p[k]>p[t],k一定在r[t]中
//若p[k]==p[t],若find(l[t],k)==1,则k在l[t]中，若find(r[t],k)==1,则k在r[t]中
bool find(int &t,int k)
{
s[t]--;
if(t==k)//t==k，t号点已找到
{
if(s[r[t]]==0 || s[l[t]]==0)s[t]=0,t=l[t]+r[t];
else get(r[t],t);
return 1;
}
bool ok=0;
if(p[k]<=p[t] && s[l[t]]>0)ok=find(l[t],k);
if(ok)return 1;
if(p[k]>=p[t] && s[r[t]]>0)ok=find(r[t],k);
if(ok)return 1;
s[t]++;//k不在t这颗树中，s[t]--就多减了，这里把它加回去
return 0;
}
void select(int t,int k)
{
if(s[r[t]]+1==k){printf("%d\n",p[t]);return;}
if(k<=s[r[t]])select(r[t],k);
else select(l[t],k-s[r[t]]-1);
}
void work()
{
int n,m,i,a,b;
s[0]=l[0]=r[0]=p[0]=0;
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d",&p[i]),insert(root,i);
char ss[10];
scanf("%d",&m);
for(i=1;i<=m && scanf("%s",ss)!=EOF;i++)
switch (ss[0])
{
case 'A':scanf("%d%d",&a,&b);
find(root,a),p[a]-=b;
if(p[a]>0)insert(root,a);
break;
case 'C':scanf("%d%d",&a,&b);
find(root,a),p[a]+=b;
insert(root,a);
break;
default:scanf("%d",&a);
if(a>s[root])printf("-1\n");
else select(root,a);
break;
}
printf("%d\n",s[root]);
}
int main()
{
init();
work();
return 0;
}