栀子花开
Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u
Description
这是一个栀子花开的季节，也是一个离别的季节，四年一千多个日日夜夜，那校园的角角落落，留下了我们沉思的身影；那上百次的成绩排名表，印证了我们深深浅浅不断进步的轨迹，但是这些进步都离不开老师的谆谆教诲。
作为计算机系的学生，算法与数据结构是必修的主干课程，因此课程的每个老师都很关心每个学生的学习情况，每天下课老师都会给某个学生进行课外辅导。首先，老师会给每个学生一个能力评定分数，如果有学生要求老师给他辅导，那老师就会专门给该同学进行课外辅导，如果没有学生要求，老师就会给评定分数最低的同学课外辅导。老师给学生辅导后，学生的能力都会有所增长，然而不同的学生增长的情况都不同。老师想知道为学生课外辅导若干天后，全班的最低分学生的编号和分数。
Input
首先第一行为T，表示有T组数据。接下来为每组数据的结构：
第一行有一个数字n，表示有n个学生，编号从1到n。(1 <= n <= 10000)。
接下来一行有n个数，分别是编号从1到n的学生的初始能力水平x，(1 <= x <= 1000)。
接下来有一行有一个数m表示老师给学生课外辅导了m天(1 <= m <= 100000)。
接下来m行，每行两个数(a b)，表示老师在第i天给编号为a同学补课，编号为a的同学能力提高了b(0 <= a <= n,1 <= b <= 1000)。如果a为0，则表示老师今天给能力最差的学生辅导。如果最低分同时有多个学生，就给编号小的学生补课。
Output
对于每组数据输出一行先输出组数(从1开始)，接着最后输出经过m天后，全班的最低分学生的编号和分数。
Sample Input
1 3 10 20 30 3
0 100 3 10 0 40
Sample Output
Case 1: 3 40
Hint
上面的数据，各个学生的能力增长情况如下：
第一天后：110 20 30
第二天后：110 20 40
第三天后：110 60 40
解题思路：用score数组来存放结点所对应的区间中所有元素的最小值。
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define lson o*2,L,(L+R)/2
#define rson o*2+1,(L+R)/2+1,R
#define mid (L+R)/2
const int maxn=11000;
int score[maxn*4];
void build_tree(int o,int L,int R){ if(L==R){ scanf("%d",&score[o]);
}else{ build_tree(lson);
build_tree(rson);
score[o]=min(score[o*2],score[o*2+1]);
}
}
void update(int o,int L,int R,int v){ if(L==R){ score[o]+=v;
}else{ if(score[o]==score[o*2])
update(lson,v);
else
update(rson,v);
score[o]=min(score[o*2],score[o*2+1]);
}
}
void Update(int o,int L,int R,int ind,int v){ if(L==R){ score[o]+=v;
}else{ if(mid>=ind){ //尽量趋近小的 Update(lson,ind,v);
}else{ Update(rson,ind,v);
}
score[o]=min(score[o*2],score[o*2+1]);
}
}
void query(int o,int L,int R){ if(L==R){ printf("%d %d\n",L,score[o]);
}else{ if(score[o]==score[o*2]){ query(lson);
}else{ query(rson);
}
}
}
int main(){ int t,cnt=0;
scanf("%d",&t);
while(t--){ int n;
scanf("%d",&n);
build_tree(1,1,n);
int m;
scanf("%d",&m);
while(m--){ int a,b;
scanf("%d%d",&a,&b);
if(a==0){ update(1,1,n,b);
}else{ Update(1,1,n,a,b);
}
}
printf("Case %d: ",++cnt);
query(1,1,n);
}
return 0;
}