FZU-1921+线段树

简单的线段树。
记录MinVal 和相应的ID即可
  1 /*
  2 线段树
  3 */
  4 #include<stdio.h>
  5 #include<string.h>
  6 #include<stdlib.h>
  7 #include<algorithm>
  8 #include<iostream>
  9 #include<queue>
 10 #include<map>
 11 #include<stack>
 12 #include<set>
 13 #include<math.h>
 14 using namespace std;
 15 typedef long long int64;
 16 //typedef __int64 int64;
 17 typedef pair<int64,int64> PII;
 18 #define MP(a,b) make_pair((a),(b)) 
 19 const int maxn = 10005;
 20 const int inf = 0x7fffffff;
 21 const double pi=acos(-1.0);
 22 const double eps = 1e-8;
 23 #define L(x) (x<<1)
 24 #define R(x) (x<<1|1)
 25 
 26 struct Tree{
 27     int l,r,id,val;
 28 }tree[ maxn<<2 ];
 29 int a[ maxn ];
 30 
 31 void build( int L,int R,int n ){
 32     tree[ n ].l = L;
 33     tree[ n ].r = R;
 34     if( L==R ){
 35         tree[ n ].id = L;
 36         tree[ n ].val = a[ L ];
 37         return ;
 38     }
 39     //tree[ n ].val = 0;
 40     int mid = (L+R)/2;
 41     build( L,mid,L(n) );
 42     build( mid+1,R,R(n) );
 43     if( tree[ L(n) ].val<tree[ R(n) ].val ) {
 44         tree[ n ].val = tree[ L(n) ].val;
 45         tree[ n ].id = tree[ L(n) ].id;
 46     }
 47     else if( tree[ L(n) ].val==tree[ R(n) ].val ){
 48         if( tree[L(n)].id<tree[R(n)].id ){
 49             tree[ n ].val = tree[ L(n) ].val;
 50             tree[ n ].id = tree[ L(n) ].id;
 51         }
 52         else {
 53             tree[ n ].val = tree[ R(n) ].val;
 54             tree[ n ].id = tree[ R(n) ].id;
 55         }
 56     }
 57     else {
 58         tree[ n ].val = tree[ R(n) ].val;
 59         tree[ n ].id = tree[ R(n) ].id;
 60     }
 61 }
 62 
 63 void update1( int val,int L,int R,int n ){
 64     if( L==R ){
 65         tree[ n ].val += val;
 66         return ;
 67     }
 68     int mid = (L+R)/2;
 69     if( tree[n].id<=mid ) update1( val,L,mid,L(n) );
 70     else update1( val,mid+1,R,R(n) );
 71     if( tree[ L(n) ].val<tree[ R(n) ].val ) {
 72         tree[ n ].val = tree[ L(n) ].val;
 73         tree[ n ].id = tree[ L(n) ].id;
 74     }
 75     else if( tree[ L(n) ].val==tree[ R(n) ].val ){
 76         if( tree[L(n)].id<tree[R(n)].id ){
 77             tree[ n ].val = tree[ L(n) ].val;
 78             tree[ n ].id = tree[ L(n) ].id;
 79         }
 80         else {
 81             tree[ n ].val = tree[ R(n) ].val;
 82             tree[ n ].id = tree[ R(n) ].id;
 83         }
 84     }
 85     else {
 86         tree[ n ].val = tree[ R(n) ].val;
 87         tree[ n ].id = tree[ R(n) ].id;
 88     }
 89 }
 90 
 91 void update2( int id,int val,int L,int R,int n ){
 92     if( L==R ){
 93         tree[ n ].val += val;
 94         return ;
 95     }
 96     int mid = (L+R)/2;
 97     if( id<=mid ) update2( id,val,L,mid,L(n) );
 98     else update2( id,val,mid+1,R,R(n) );
 99     if( tree[ L(n) ].val<tree[ R(n) ].val ) {
100         tree[ n ].val = tree[ L(n) ].val;
101         tree[ n ].id = tree[ L(n) ].id;
102     }
103     else if( tree[ L(n) ].val==tree[ R(n) ].val ){
104         if( tree[L(n)].id<tree[R(n)].id ){
105             tree[ n ].val = tree[ L(n) ].val;
106             tree[ n ].id = tree[ L(n) ].id;
107         }
108         else {
109             tree[ n ].val = tree[ R(n) ].val;
110             tree[ n ].id = tree[ R(n) ].id;
111         }
112     }
113     else {
114         tree[ n ].val = tree[ R(n) ].val;
115         tree[ n ].id = tree[ R(n) ].id;
116     }
117 }
118 
119 void query( int L,int R,int n ){
120     if( L==R ) return ;
121     int mid = (L+R)/2;
122     query( L,mid,L(n) );
123     query( mid+1,R,R(n) );
124     if( tree[ L(n) ].val<tree[ R(n) ].val ) {
125         tree[ n ].val = tree[ L(n) ].val;
126         tree[ n ].id = tree[ L(n) ].id;
127     }
128     else if( tree[ L(n) ].val==tree[ R(n) ].val ){
129         if( tree[L(n)].id<tree[R(n)].id ){
130             tree[ n ].val = tree[ L(n) ].val;
131             tree[ n ].id = tree[ L(n) ].id;
132         }
133         else {
134             tree[ n ].val = tree[ R(n) ].val;
135             tree[ n ].id = tree[ R(n) ].id;
136         }
137     }
138     else {
139         tree[ n ].val = tree[ R(n) ].val;
140         tree[ n ].id = tree[ R(n) ].id;
141     }
142 }
143 
144 int main(){
145     int T;
146     int Case = 1;
147     scanf("%d",&T);
148     while( T-- ){
149         int n;
150         scanf("%d",&n);
151         for( int i=1;i<=n;i++ )
152             scanf("%d",&a[i]);
153         build( 1,n,1 );
154         int m;
155         scanf("%d",&m);
156         int x,y;
157         while( m-- ){
158             scanf("%d%d",&x,&y);
159             if( x==0 ) update1( y,1,n,1 );
160             else update2( x,y,1,n,1 );
161         }
162         query( 1,n,1 );
163         printf("Case %d: %d %d
",Case++,tree[1].id,tree[1].val);
164     }
165     return 0;
166 }
View Code
keep moving...