「NOIP模拟赛」魔兽争霸
小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 |
| 51 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 |
45
-1 11 3
|
约定
40%的数据 n<=3000 m<=5000
70%的数据 n<=8000 m<=10000
100%的数据 n<=30000 m<=50000
90%的数据随机生成
食尸鬼HP没有上限
数据保证任意时刻食尸鬼的HP值在longint范围内
数据保证A和C命令中的食尸鬼是活着的
输入数据中没有多余空格、换行
题解
部分分快排。。
正解平衡树
|
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 |
#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<map> #include<algorithm> #define ll long long using namespace std; int read() { int 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; } int tmp; int n,m,root,size; int b[300005],v[300005],w[300005],s[300005],rnd[300005]; int ls[300005],rs[300005]; bool tag[300005]; void update(int k){s[k]=s[ls[k]]+s[rs[k]]+w[k];} void rturn(int &k) {int t=ls[k];ls[k]=rs[t];rs[t]=k;update(k);update(t);k=t;} void lturn(int &k) {int t=rs[k];rs[k]=ls[t];ls[t]=k;update(k);update(t);k=t;} void insert(int &k,int num) { if(!k){k=++size;rnd[k]=rand();w[k]=s[k]=1;v[k]=num;return;} s[k]++; if(num==v[k]){w[k]++;return;} else if(num<v[k]){insert(ls[k],num);if(rnd[ls[k]]<rnd[k])rturn(k);} else {insert(rs[k],num);if(rnd[rs[k]]<rnd[k])lturn(k);} } void del(int &k,int num) { if(!k)return; if(num==v[k]) { if(w[k]>1){w[k]--;s[k]--;return;} if(ls[k]*rs[k]==0)k=ls[k]+rs[k]; else if(rnd[ls[k]]<rnd[rs[k]]){rturn(k);del(k,num);} else {lturn(k);del(k,num);} } else if(num<v[k]) {del(ls[k],num);s[k]--;} else {del(rs[k],num);s[k]--;} } int query(int k,int x) { if(!k)return -1; if(s[ls[k]]>=x)return query(ls[k],x); else if(x>s[ls[k]]+w[k])return query(rs[k],x-w[k]-s[ls[k]]); else return k; } int main() { //freopen("war.in","r",stdin); //freopen("war.out","w",stdout); n=read(); for(int i=1;i<=n;i++)b[i]=read(); for(int i=1;i<=n;i++)insert(root,b[i]); m=read(); int k,x; for(int i=1;i<=m;i++) { char ch[2]; scanf("%s",ch); if(ch[0]=='A') { k=read();x=read(); del(root,b[k]);b[k]-=x; if(b[k]>0)insert(root,b[k]); else n--; } else if(ch[0]=='C') { k=read();x=read(); del(root,b[k]);b[k]+=x; insert(root,b[k]); } else { k=read(); if(k>n)puts("-1"); else printf("%d\n",v[query(root,n-k+1)]); } } printf("%d\n",n); return 0; } |
计数器 9787035
OI 课件=>
OI 课件=>
突然想吐槽C党的标准库，P党泪奔呀=_=….