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;  
}