2014.10.6模拟赛【魔兽争霸】-白红宇

2014.10.6模拟赛【魔兽争霸】

阅读量：4588 次

发布时间：2019-06-09

本文共 3661 字，大约阅读时间需要 12 分钟。

魔兽争霸(war.pas)

小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

1 2 3

4 5

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

-1

约定

40%的数据 n<=3000 m<=5000

70%的数据 n<=8000 m<=10000

100%的数据 n<=30000 m<=50000

90%的数据随机生成

食尸鬼HP没有上限

数据保证任意时刻食尸鬼的HP值在longint范围内

数据保证A和C命令中的食尸鬼是活着的

输入数据中没有多余空格、换行

听说这是难度noip普及组的模拟赛啊……为毛有平衡树

支持三种操作：插入，删除，第k大。

还要保存一下原来编号i的食尸鬼在treap中的节点编号

唉考场上贴了模板结果后面处理的不对还是爆蛋

也就200行

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              #include
               
                #define LL long long#define inf 0x7ffffff#define pa pair
                
                 #define pi 3.1415926535897932384626433832795028841971#define N 100010using namespace std;inline LL read(){ LL x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f;}struct node{ int l,r,num,rando,sons,rep;}tree[N];int treesize,root,n,m,ans,tot;int from[N];void update(int now){ tree[now].sons = tree[tree[now].l].sons + tree[tree[now].r].sons + tree[now].rep;}void right_rotate(int &work){ int t = tree[work].l; tree[work].l = tree[t].r; tree[t].r = work; tree[t].sons = tree[work].sons; update(work); work = t;} void left_rotate(int &work){ int t = tree[work].r; tree[work].r = tree[t].l; tree[t].l = work; tree[t].sons = tree[work].sons; update(work); work = t;} int insert(int &now,int x){ if (now == 0) { now = ++treesize; tree[now].rando = rand(); tree[now].num = x; tree[now].rep=tree[now].sons = 1; return now; } tree[now].sons++; int save=now; if (tree[now].num==x) { tree[now].rep++; return now; } if (x < tree[now].num) { save=insert(tree[now].l,x); if (tree[tree[now].l].rando < tree[now].rando) right_rotate(now); } else { save=insert(tree[now].r,x); if (tree[tree[now].r].rando < tree[now].rando) left_rotate(now); } return save;} void del(int &now,int x){ if (now == 0) return; if (tree[now].num==x) { if (tree[now].rep>1) { tree[now].rep--; tree[now].sons--; return; } if (tree[now].l*tree[now].r==0) now=tree[now].l+tree[now].r; else if (tree[tree[now].l].rando
                 
                  tree[now].num) { tree[now].sons--; del(tree[now].r,x); } else { tree[now].sons--; del(tree[now].l,x); }}int ask_rank(int now,int x){ if (now==0) return 0; if (tree[now].num==x) return tree[tree[now].l].sons+1; else if (x>tree[now].num) return tree[tree[now].l].sons+tree[now].rep+ask_rank(tree[now].r,x); else return ask_rank(tree[now].l,x);}int ask_num(int now,int x){ if (tree[now].sons
                  
                   tree[tree[now].l].sons+tree[now].rep)return ask_num(tree[now].r,x-tree[tree[now].l].sons-tree[now].rep); else return tree[now].num;}void succ(int now,int x){ if(now==0)return; if(tree[now].num
                   
                    x){ans=tree[now].num;pred(tree[now].l,x);} else pred(tree[now].r,x);}int main(){ freopen("war.in","r",stdin); freopen("war.out","w",stdout); srand(time(0)); n=read();tot=n; for (int i=1;i<=n;i++) { int x=read(); from[i]=insert(root,x); } m=read(); for (int i=1;i<=m;i++) { char ch=getchar(); while (ch!='A'&&ch!='C'&&ch!='Q')ch=getchar(); if (ch=='Q') { int x=read(); if (x>tot)printf("-1\n"); else cout<
                    
                     <