司马称好时间限制(普通/Java) : 2000 MS/ 6000 MS 运行内存限制 : 65536 KByte
总提交 : 36 测试通过 : 6 描述
汉朝时期，司马徽从不说别人的短处，与人说话时，从来不问别人的好恶，都说好话。一个同乡来问他安否，他回答好。有一个说自己的儿子死了，他也说大好。妻子骂他缺德，别人死了儿子为什么还要说好，司马徽说：“你的话也太好了。”
————成语《司马称好》的由来
CH=称好？ 对于这个同音问题，霸气侧漏的CH感到无比的愤慨，于是他亲自出马，教导司马微，教他算法，希望他从算法中领悟出做人的道理。
CH的第一堂课是学习黑箱测试法：CH动态的给出若干个操作，操作种类如下，
GET：第一次执行GET时，返回黑箱中第1小的元素，第二次执行GET时，返回黑箱中第2小的元素，第三次执行GET时返回黑箱中第3小的元素，依此类推......
ADD(val)：在黑箱中插入数值为val的元素
CHG(i,j)：把第i次插入的元素更改为j
下面，展示的便是样例中的操作执行过程
操作 第i小 黑箱中的元素 输出值
1 ADD(3) 0 3
2 GET 1 3 3
3 ADD(1) 1 1, 3
4 GET 2 1, 3 3
5 ADD(-4) 2 -4, 1, 3
6 ADD(2) 2 -4, 1, 2, 3
7 ADD(8) 2 -4, 1, 2, 3, 8
8 ADD(-1000) 2 -1000, -4, 1, 2, 3, 8
9 GET 3 -1000, -4, 1, 2, 3, 8 1
10 GET 4 -1000, -4, 1, 2, 3, 8 2
11 ADD(2) 4 -1000, -4, 1, 2, 2, 3, 8
12 CHG(6,-500) 4 -500, -4, 1, 2, 2, 3, 8 输入
第一行为整数n,表示一共有n个操作， 接下来的n行，每行开头是一个字符串S，表示操作的类型： 若S为GET，则输出当前第i小的元素， 若S为ADD(val)，表示黑箱中加入值为val的元素 若S为CHG(i,j)，表示把第i次插入的元素更改为j
其中,0 < n <= 500000， val和j为int型，数据保证合法
输出
对于每个GET，输出当前第i小的元素值。 样例输入 12 样例输出 3 题目来源 YB |
http://218.194.91.48/acmhome/problemdetail.do?&method=showdetail&id=1165
很久之前做的题目，代码有点搓~~
但确实算是比较经典的题目了~~ 适合刚学堆的童鞋练练手~~
做法很简单，建立两个堆。一个最大堆，一个最小堆。
显然，最大堆存的是前n小的数，最小堆存的是后m-n大的数（假设m是数字总数，n表示询问的次数）。
也就是说，最小堆内所有数都比最大堆内的所有数还要大。
比较麻烦的处理是，更改第i个输入时，需要找到已改变位置的原数新位置，所以需要双向记录路径。
容易错的是，两个堆内的数，有时需要相互传递。即有可能出现最大堆的堆顶比最小堆的堆顶还要大，因此需要两个堆顶互换位置。
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int cnt1=0,cnt2=0,cnt=0;
struct Mark{
int gt,f;
}s1[600000],s2[600000],gt[600000];
void add1(int v){
if(v==1) return;
if(s1[v].f>=s1[v>>1].f) return ;
swap(s1[v],s1[v>>1]);
gt[s1[v].gt].gt=v;
gt[s1[v>>1].gt].gt=v>>1;
add1(v>>1);
}
void add2(int v){
if(v==1) return;
if(s2[v].f<=s2[v>>1].f) return ;
swap(s2[v],s2[v>>1]);
gt[s2[v].gt].gt=v;
gt[s2[v>>1].gt].gt=v>>1;
add2(v>>1);
}
void change1(int v){
int l=v<<1;
if(l<cnt1)
if(s1[l].f>s1[l+1].f) l++;
if(l>cnt1) return;
if(s1[l].f>=s1[v].f) return ;
swap(s1[v],s1[l]);
gt[s1[v].gt].gt=v;
gt[s1[l].gt].gt=l;
change1(l);
}
void change2(int v){
int l=v<<1;
if(l<cnt2)
if(s2[l].f<s2[l+1].f) l++;
if(l>cnt2) return;
if(s2[l].f<=s2[v].f) return ;
swap(s2[v],s2[l]);
gt[s2[v].gt].gt=v;
gt[s2[l].gt].gt=l;
change2(l);
}
int main(){
// freopen("01.in","r",stdin);
// freopen("02.out","w",stdout);
int n,i,t,val,flag=0;
char str[40];
scanf("%d",&n);
while(n--){
scanf("%s",str);
// puts(str);
if(str[0]=='A'){
val=0;
if(str[4]=='-') i=5;
else i=4;
for(;str[i]!=')';i++){
val*=10;
val+=str[i]-'0';
}
if(str[4]=='-') val=0-val;
cnt++;
cnt1++;
gt[cnt].gt=cnt1;
gt[cnt].f=1;
s1[cnt1].f=val;
s1[cnt1].gt=cnt;
add1(cnt1);
}
else if(str[0]=='G'){
cnt2++;
s2[cnt2]=s1[1];
gt[s1[1].gt].f=2;
gt[s1[1].gt].gt=cnt2;
if(cnt1>1){
s1[1]=s1[cnt1];
gt[s1[cnt1].gt].gt=1;
change1(1);
}
cnt1--;
add2(cnt2);
if(cnt1 && cnt2)
while(s1[1].f<s2[1].f){
swap(s1[1],s2[1]);
gt[s1[1].gt].f=1;
gt[s2[1].gt].f=2;
change1(1);
change2(1);
}
printf("%d\n",s2[1].f);
}
else {
t=0;
val=0;
for(i=4;str[i]!=',';i++){
t*=10;
t+=str[i]-'0';
}
flag=0;
if(str[++i]=='-'){
i++;
flag=1;
}
for(;str[i]!=')';i++){
val*=10;
val+=str[i]-'0';
}
if(flag) val=0-val;
if(gt[t].f==1){
s1[gt[t].gt].f=val;
change1(gt[t].gt);
add1(gt[t].gt);
}
else{
s2[gt[t].gt].f=val;
change2(gt[t].gt);
add2(gt[t].gt);
}
}
// printf("--add: %d --max: %d\n",cnt,cnt2);
// printf("--s1: ");for(i=1;i<=cnt1;i++)printf("%d ",s1[i].f);printf("\n");
// printf("--s2: ");for(i=1;i<=cnt2;i++)printf("%d ",s2[i].f);printf("\n");
}
return 0;
}
/* 随机
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstdlib>
using namespace std;
int main(){
// freopen("01.in","w",stdout);
int t,n=10000,cnt=0,now=0;
printf("10000\n");
while(n--){
t=rand()%3;
if(t==0){
if(now<cnt){
now++;
printf("GET\n");
}
else t=1;
}
if(t==1){
if(cnt==0) t=2;
else printf("CHG(%d,%d)\n",rand()%cnt+1,rand()%2000-1000);
}
if(t==2){
cnt++;
printf("ADD(%d)\n",rand()%2000-1000);
}
}
return 0;
}
*/
/* 暴力
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int cnt=0,s[1000000],num=0,s1[1000000];
int main(){
// freopen("01.in","r",stdin);
// freopen("01.out","w",stdout);
int n,i,t,val,flag=0;
char str[40];
scanf("%d",&n);
while(n--){
scanf("%s",str);
if(str[0]=='A'){
val=0;
if(str[4]=='-') i=5;
else i=4;
for(;str[i]!=')';i++){
val*=10;
val+=str[i]-'0';
}
if(str[4]=='-') val=0-val;
s[cnt++]=val;
}
else if(str[0]=='G'){
for(i=0;i<cnt;i++)
s1[i]=s[i];
sort(s1,s1+cnt);
printf("%d\n",s1[num++]);
}
else {
t=0;
val=0;
for(i=4;str[i]!=',';i++){
t*=10;
t+=str[i]-'0';
}
flag=0;
if(str[++i]=='-'){
i++;
flag=1;
}
for(;str[i]!=')';i++){
val*=10;
val+=str[i]-'0';
}
if(flag) val=0-val;
s[t-1]=val;
}
}
return 0;
}
*/