FZU-1921+线段树

简单的线段树。

记录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 = 10005;
const int inf = 0x7fffffff;
const double pi=acos(-1.0);
const double eps = 1e-8;
#define L(x) (x<<1)
#define R(x) (x<<1|1)

struct Tree{
	int l,r,id,val;
}tree[ maxn<<2 ];
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)/2;
	build( L,mid,L(n) );
	build( mid+1,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)/2;
	if( tree[n].id<=mid ) update1( val,L,mid,L(n) );
	else update1( val,mid+1,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)/2;
	if( id<=mid ) update2( id,val,L,mid,L(n) );
	else update2( id,val,mid+1,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)/2;
	query( L,mid,L(n) );
	query( mid+1,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 = 1;
	scanf("%d",&T);
	while( T-- ){
		int n;
		scanf("%d",&n);
		for( int i=1;i<=n;i++ )
			scanf("%d",&a[i]);
		build( 1,n,1 );
		int m;
		scanf("%d",&m);
		int x,y;
		while( m-- ){
			scanf("%d%d",&x,&y);
			if( x==0 ) update1( y,1,n,1 );
			else update2( x,y,1,n,1 );
		}
		query( 1,n,1 );
		printf("Case %d: %d %d\n",Case++,tree[1].id,tree[1].val);
	}
	return 0;
}