Problem 1921 栀子花开
Accept: 216 Submit: 745
Time Limit: 1000 mSec Memory Limit : 32768 KB
Problem Description
这是一个栀子花开的季节，也是一个离别的季节，四年一千多个日日夜夜，那校园的角角落落，留下了我们沉思的身影；那上百次的成绩排名表，印证了我们深深浅浅不断进步的轨迹，但是这些进步都离不开老师的谆谆教诲。
作为计算机系的学生，算法与数据结构是必修的主干课程，因此课程的每个老师都很关心每个学生的学习情况，每天下课老师都会给某个学生进行课外辅导。首先，老师会给每个学生一个能力评定分数，如果有学生要求老师给他辅导，那老师就会专门给该同学进行课外辅导，如果没有学生要求，老师就会给评定分数最低的同学课外辅导。老师给学生辅导后，学生的能力都会有所增长，然而不同的学生增长的情况都不同。老师想知道为学生课外辅导若干天后，全班的最低分学生的编号和分数。
Input
首先第一行为T，表示有T组数据。接下来为每组数据的结构：
第一行有一个数字n，表示有n个学生，编号从1到n。(1 <= n <= 10000)。
接下来一行有n个数，分别是编号从1到n的学生的初始能力水平xi，(1 <= xi <= 1000)。
接下来有一行有一个数m表示老师给学生课外辅导了m天(1 <= m <= 100000)。
接下来m行，每行两个数(ai bi)，表示老师在第i天给编号为ai同学补课，编号为ai的同学能力提高了bi(0 <= ai <= n,1 <= bi <= 1000)。如果ai为0，则表示老师今天给能力最差的学生辅导。如果最低分同时有多个学生，就给编号小的学生补课。
Output
对于每组数据输出一行先输出组数(从1开始)，接着最后输出经过m天后，全班的最低分学生的编号和分数。
Sample Input
1310 20 3030 1003 100 40
Sample Output
Case 1: 3 40
Hint
上面的数据，各个学生的能力增长情况如下：
第一天后：110 20 30
第二天后：110 20 40
第三天后：110 60 40
Source
FOJ有奖月赛-2010年06月
传送门：【FZU】1921 栀子花开
题目分析：不多说，线段树果题，维护区间最小，相同最小往左儿子身上走。
不知道是不是我没看清题意
，你说输出的时候要是有相同最小的我该怎么输出
。。。反正我不管了，就输出最左端的。。。。
代码如下：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;
typedef long long Int ;
#define ls ( o << 1 )
#define rs ( o << 1 | 1 )
#define rt l , r , o
#define root 1 , n , 1
#define lson l , m , ls
#define rson m + 1 , r , rs
#define mid ( ( l + r ) >> 1 )
#define clear( A , X ) memset ( A , X , sizeof A )
const int maxN = 10005 ;
const int oo = 0x3f3f3f3f ;
int mmin[maxN << 2] ;
int min ( const int X , const int Y ) {
if ( X < Y ) return X ;
return Y ;
}
void PushUp ( int o ) {
mmin[o] = min ( mmin[ls] , mmin[rs] ) ;
}
void Build ( int l , int r , int o ) {
if ( l == r ) {
scanf ( "%d" , &mmin[o] ) ;
return ;
}
int m = mid ;
Build ( lson ) ;
Build ( rson ) ;
PushUp ( o ) ;
}
void Update ( int pos , int val , int l , int r , int o ) {
if ( l == r ) {
mmin[o] += val ;
return ;
}
int m = mid ;
if ( !pos ) {
if ( mmin[ls] <= mmin[rs] ) Update ( pos , val , lson ) ;
else Update ( pos , val , rson ) ;
}
else{
if ( pos <= m ) Update ( pos , val , lson ) ;
else Update ( pos , val , rson ) ;
}
PushUp ( o ) ;
}
void Query ( int l , int r , int o ) {
if ( l == r ) {
printf ( "%d %d\n" , l , mmin[o] ) ;
return ;
}
int m = mid ;
if ( mmin[ls] <= mmin[rs] ) Query ( lson ) ;
else Query ( rson ) ;
}
void work () {
int n , m , x , v ;
scanf ( "%d" , &n ) ;
Build ( root ) ;
scanf ( "%d" , &m ) ;
while ( m -- ) {
scanf ( "%d%d" , &x , &v ) ;
Update ( x , v , root ) ;
}
Query ( root ) ;
}
int main () {
int T , cas ;
for ( scanf ( "%d" , &T ) , cas = 1 ; cas <= T ; ++ cas ) {
printf ( "Case %d: " , cas ) ;
work () ;
}
return 0 ;
}