题目传送门

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。每个一行数。
最后一行输出一个数：战斗结束后剩余的食尸鬼数

Sample Input

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

Sample Output

4
5
-1
11
3

HINT

40%的数据  n<=3000  m<=5000
70%的数据  n<=8000  m<=10000
100%的数据  n<=30000  m<=50000
90%的数据随机生成
食尸鬼HP没有上限
数据保证任意时刻食尸鬼的HP值在10^7范围内
数据保证A和C命令中的食尸鬼是活着的
输入数据中没有多余空格、换行

思路：

我们可以开一个数组用来记录每个食尸鬼的HP 每次修改现修改数组里的值 ，然后删除treap中的这个食尸鬼
如果这个食尸鬼死亡(即HP<=0)就扔掉不管，否则还是要把它扔回去的
so，某个食尸鬼被增加HP的话修改方法同理
为了支持查询，我们要记录子树大小，以便于从根向下查找第k大值，注意，是第k大值，一定要与第k小值区分好

#include<cstdio>
#include<cstring>
#include<ctime>
#include<algorithm>
using namespace std;
struct your
{
    int l,r,v,rnd,w,s;
}a[200000];
int root,tot;
void push(int k)
{
    a[k].s=a[k].w+a[a[k].l].s+a[a[k].r].s;
}
void lturn(int &k)
{
    int t=a[k].r;
    a[k].r=a[t].l;
    a[t].l=k;
    push(k);push(t);
    k=t;
}
void rturn(int &k)
{
    int t=a[k].l;
    a[k].l=a[t].r;
    a[t].r=k;
    push(k);push(t);
    k=t;
}
void update(int &k,int temp)
{
    if(!k)
    {
        k=++tot;
        a[k].w=a[k].s=1;
        a[k].v=temp;
        a[k].rnd=rand();
        return ;
    }
    a[k].s++;
    if(temp==a[k].v) a[k].w++;
    else if(temp<a[k].v)
    {
        update(a[k].l,temp);
        if(a[a[k].l].rnd<a[k].rnd) rturn(k);
    } 
    else
    {
        update(a[k].r,temp);
        if(a[a[k].r].rnd<a[k].rnd) lturn(k);
    }
}
void del(int &k,int temp)
{
    if(!k)return ;
    if(temp==a[k].v)
    {
        if(a[k].w>1) a[k].w--,a[k].s--;
        else if(a[k].l*a[k].r==0)
                k=a[k].l+a[k].r;
        else if(a[a[k].l].rnd<a[a[k].r].rnd)
                rturn(k),del(k,temp);
        else lturn(k),del(k,temp);
    }
    else if(temp<a[k].v) del(a[k].l,temp),a[k].s--;
    else del(a[k].r,temp),a[k].s--;
}
int ask(int k,int temp)
{
    if(a[a[k].l].s>=temp)return ask(a[k].l,temp);
    else if(temp>a[a[k].l].s+a[k].w)return ask(a[k].r,temp-a[k].w-a[a[k].l].s);
    else return k;
}
int n,m;
char s[2];
int hp[31000];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&hp[i]);
    for(int i=1;i<=n;i++)
        update(root,hp[i]);
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%s",&s[0]);
        if(s[0]=='A')
        {
            int tmp,c;
            scanf("%d%d",&tmp,&c);
            del(root,hp[tmp]);
            hp[tmp]-=c;
            if(hp[tmp]>0) 
                update(root,hp[tmp]);
            else n--;
        }
        else if(s[0]=='C')
        {
            int tmp,c;
            scanf("%d%d",&tmp,&c);
            del(root,hp[tmp]);
            hp[tmp]+=c;
            update(root,hp[tmp]);
        }
        else
        {
            int tmp;
            scanf("%d",&tmp);
            if(tmp>n)printf("-1\n");
            else printf("%d\n",a[ask(root,n-tmp+1)].v);
        }
    }
    printf("%d",n);
}