简单的线段树。
记录MinVal 和 相应的ID即可
/*
线段树
*/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<iostream>
#include<queue>
#include<map>
#include<stack>
#include<set>
#include<math.h>
using namespace std;
typedef long long int64;
//typedef __int64 int64;
typedef pair<int64,int64> PII;
#define MP(a,b) make_pair((a),(b))
const int maxn = ;
const int inf = 0x7fffffff;
const double pi=acos(-1.0);
const double eps = 1e-;
#define L(x) (x<<1)
#define R(x) (x<<1|1) struct Tree{
int l,r,id,val;
}tree[ maxn<< ];
int a[ maxn ]; void build( int L,int R,int n ){
tree[ n ].l = L;
tree[ n ].r = R;
if( L==R ){
tree[ n ].id = L;
tree[ n ].val = a[ L ];
return ;
}
//tree[ n ].val = 0;
int mid = (L+R)/;
build( L,mid,L(n) );
build( mid+,R,R(n) );
if( tree[ L(n) ].val<tree[ R(n) ].val ) {
tree[ n ].val = tree[ L(n) ].val;
tree[ n ].id = tree[ L(n) ].id;
}
else if( tree[ L(n) ].val==tree[ R(n) ].val ){
if( tree[L(n)].id<tree[R(n)].id ){
tree[ n ].val = tree[ L(n) ].val;
tree[ n ].id = tree[ L(n) ].id;
}
else {
tree[ n ].val = tree[ R(n) ].val;
tree[ n ].id = tree[ R(n) ].id;
}
}
else {
tree[ n ].val = tree[ R(n) ].val;
tree[ n ].id = tree[ R(n) ].id;
}
} void update1( int val,int L,int R,int n ){
if( L==R ){
tree[ n ].val += val;
return ;
}
int mid = (L+R)/;
if( tree[n].id<=mid ) update1( val,L,mid,L(n) );
else update1( val,mid+,R,R(n) );
if( tree[ L(n) ].val<tree[ R(n) ].val ) {
tree[ n ].val = tree[ L(n) ].val;
tree[ n ].id = tree[ L(n) ].id;
}
else if( tree[ L(n) ].val==tree[ R(n) ].val ){
if( tree[L(n)].id<tree[R(n)].id ){
tree[ n ].val = tree[ L(n) ].val;
tree[ n ].id = tree[ L(n) ].id;
}
else {
tree[ n ].val = tree[ R(n) ].val;
tree[ n ].id = tree[ R(n) ].id;
}
}
else {
tree[ n ].val = tree[ R(n) ].val;
tree[ n ].id = tree[ R(n) ].id;
}
} void update2( int id,int val,int L,int R,int n ){
if( L==R ){
tree[ n ].val += val;
return ;
}
int mid = (L+R)/;
if( id<=mid ) update2( id,val,L,mid,L(n) );
else update2( id,val,mid+,R,R(n) );
if( tree[ L(n) ].val<tree[ R(n) ].val ) {
tree[ n ].val = tree[ L(n) ].val;
tree[ n ].id = tree[ L(n) ].id;
}
else if( tree[ L(n) ].val==tree[ R(n) ].val ){
if( tree[L(n)].id<tree[R(n)].id ){
tree[ n ].val = tree[ L(n) ].val;
tree[ n ].id = tree[ L(n) ].id;
}
else {
tree[ n ].val = tree[ R(n) ].val;
tree[ n ].id = tree[ R(n) ].id;
}
}
else {
tree[ n ].val = tree[ R(n) ].val;
tree[ n ].id = tree[ R(n) ].id;
}
} void query( int L,int R,int n ){
if( L==R ) return ;
int mid = (L+R)/;
query( L,mid,L(n) );
query( mid+,R,R(n) );
if( tree[ L(n) ].val<tree[ R(n) ].val ) {
tree[ n ].val = tree[ L(n) ].val;
tree[ n ].id = tree[ L(n) ].id;
}
else if( tree[ L(n) ].val==tree[ R(n) ].val ){
if( tree[L(n)].id<tree[R(n)].id ){
tree[ n ].val = tree[ L(n) ].val;
tree[ n ].id = tree[ L(n) ].id;
}
else {
tree[ n ].val = tree[ R(n) ].val;
tree[ n ].id = tree[ R(n) ].id;
}
}
else {
tree[ n ].val = tree[ R(n) ].val;
tree[ n ].id = tree[ R(n) ].id;
}
} int main(){
int T;
int Case = ;
scanf("%d",&T);
while( T-- ){
int n;
scanf("%d",&n);
for( int i=;i<=n;i++ )
scanf("%d",&a[i]);
build( ,n, );
int m;
scanf("%d",&m);
int x,y;
while( m-- ){
scanf("%d%d",&x,&y);
if( x== ) update1( y,,n, );
else update2( x,y,,n, );
}
query( ,n, );
printf("Case %d: %d %d\n",Case++,tree[].id,tree[].val);
}
return ;
}