本文主要是介绍巴蜀1471 魔兽争霸，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Description
小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向你发出询问 Input 第一行，一个正整数 n ，以后n个整数 表示n个食尸鬼的初始HP值，接着一个正整数m ，以下m行
每行一个小x发出的信号 Output
对于小x的每个询问，输出HP第k多的食尸鬼有多少HP，如果食尸鬼总数，不足k个，输出-1。每个一行数。
最后一行输出一个数：战斗结束后剩余的食尸鬼数
平衡树模板题。唯一多出来的是修改。
没有特别好的方法，删除之后再插入。
直接用数组下标表示编号比较好写。
#include<cstdio>
#include<cstring>
struct node
{int f,c[2],x,s;
}t[31000];
int r;
void up(int p)
{t[p].s=t[t[p].c[0]].s+t[t[p].c[1]].s+1;
}
void rot(int p,bool b)
{int x=t[p].f;int y=t[p].c[b];int z=t[y].c[!b];if (x) t[x].c[t[x].c[1]==p]=y;t[p].f=y;t[y].c[!b]=p;t[p].c[b]=z;if (z) t[z].f=p;t[y].f=x;up(p);up(y);
}
void splay(int p)
{int x,y,z;while (t[p].f){x=t[p].f;if (!t[x].f){rot(x,t[x].c[1]==p);break;}y=t[x].f;if ((t[y].c[0]==x)^(t[x].c[0]==p)){rot(x,t[x].c[1]==p);rot(y,t[y].c[1]==p);}else{rot(y,t[y].c[1]==x);rot(x,t[x].c[1]==p);}}r=p;
}
void ins(int id)
{int p=r,f,y,z;bool b;if (!p){r=id;t[r].s=1;t[r].f=0;t[r].c[0]=t[r].c[1]=0;return;}while (p){if (t[id].x<t[p].x)f=p,p=t[p].c[0],b=0;else f=p,p=t[p].c[1],b=1;}t[id].f=f;t[f].c[b]=id;t[id].s=1;t[id].c[0]=t[id].c[1]=0;while (f) up(f),f=t[f].f;splay(id);
}
void del(int p)
{splay(p);if (t[p].c[0]*t[p].c[1]==0){r=t[p].c[0]+t[p].c[1];t[t[p].c[0]].f=t[t[p].c[1]].f=0;return;}int x=t[p].c[0],y=t[p].c[1];t[x].f=0;while (t[x].c[1]) x=t[x].c[1];splay(x);t[x].c[1]=y;t[y].f=x;up(x);
}
void mod(int id,int x)
{t[id].x+=x;del(id);if (t[id].x>0) ins(id);
}
int que(int k)
{int p=r;if (t[p].s<k) return -1;while (1){if (k<=t[t[p].c[1]].s) p=t[p].c[1];else{if (k==t[t[p].c[1]].s+1){splay(p);return t[p].x;}else k-=(t[t[p].c[1]].s+1),p=t[p].c[0];}}
}
int main()
{int i,j,k,m,n,x,y,z;char c[5];scanf("%d",&n);for (i=1;i<=n;i++){scanf("%d",&t[i].x);ins(i);}scanf("%d",&m);for (i=1;i<=m;i++){scanf("%s",c+1);if (c[1]=='A')scanf("%d%d",&x,&y),mod(x,-y);if (c[1]=='C')scanf("%d%d",&x,&y),mod(x,y);if (c[1]=='Q')scanf("%d",&x),printf("%d\n",que(x));}printf("%d\n",t[r].s);
}这篇关于巴蜀1471 魔兽争霸的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
