Segment tree
I will talk about the structure called the segment tree and give its simple implementation in C ++. This structure is very useful in cases when it is necessary to frequently look for the value of a function on segments of a linear array and to be able to quickly change the values ​​of a group of consecutive elements.
A typical example of a problem on a segment tree:
There is a linear array, initially filled with some data. Next come 2 types of requests:
1st type - find the value of the maximum element on the segment of the array [a..b].
2nd type - replace the ith element of the array with x.
The query “add x to all elements on the segment [a..b]” is possible, but in this article I do not consider it.
With the help of a tree of segments, one can search not only for the maximum of numbers, but also for any function satisfying the associativity property.
This limitation is due to the fact that the values ​​are predicted for some segments.
You can also search, for example, not the values, but the sequence numbers of the elements.
It is desirable that the function had a “neutral” argument that does not affect the result. For example, for the sum this number is 0: (a + 0 = a), and for the maximum it is infinity: max (a, -inf) = a.
So let's go.
The easiest (and slowest) way to solve the above problem is to start a linear array, and humbly do what they want from us.
With this implementation, the time to find the answer to the request is of the order O (n). on average, you will have to walk through half of the array to find the maximum. Although there are positive moments - changing the value of an element requires O (1) time. This algorithm can be accelerated by 2 times, if we perform a small pre-calculation: for each pair of elements we find the value of the maximum of them, and write it into another array. Then, when searching for the maximum in the segment, for each pair of elements the value of the larger is already known, and you will only have to compare it. it remains only to carefully check the boundary elements, since the boundary of the requested segment is not necessarily even.
The figure highlights the items that need to be checked.
It is clear that over these arrays you can enter another one, so that the search would be 2 times faster, and over it another one ... and so on until the topmost array will not consist of one element. As it is not difficult to guess, the value of a single element in the topmost array is the value of the maximum element.
')
Some explanations: the number near the top of the tree is the position of this top in the real array. With this implementation of tree storage, it is very convenient to look for the ancestor and descendants of a vertex: the ancestor of the vertex i has the number i / 2, and the descendants of the number i * 2 and i * 2 + 1. The figure shows that it is necessary that the length of the array is a power of two. If this is not the case, then the array can be supplemented with neutral elements at the end. Memory consumption of the storage structure from 2n to 4n, (n - the number of elements).
The search algorithm “from above” (there is also “below”) is very simple both in understanding and implementation (although it may confuse those who are not familiar with recursion).
The algorithm is as follows:
We start the survey from the top 1 (the top one).
1. Let the current vertex know the maximum on the interval l..r.
“The areas [a..b] and [l..r] intersect?”
possible options:
a. do not intersect at all.
so as not to affect the result of the calculation, we will return the neutral element (infinity).
b. the region [l..r] completely lies inside [a..b].
return the calculated value at the current vertex.
with. another way to overlap areas.
ask the same for the children of the current vertex and calculate the maximum among them (see the code if it is not clear).
As you can see, the algorithm is short, but recursive. The time complexity is O (logN), which is much more ray than O (N). for example, with an array of 10 ^ 9 elements, about 32 comparisons are needed.
Changing the number in this structure is even easier - you have to go through all the vertices from the given one to the 1st, and if the value in the current is less than the new, then replace it. It also takes O (log N) time.
The implementation of the algorithm.
It is assumed that the number of elements in the array is no more than 1024 (numbers 0..1023).
That, in general, is all that is necessary to know first about the segment tree.
For a change, you can still deal with the calculation algorithm “from below” (which, by the way, is non-recursive), although I find it less attractive. Well and, of course, it is worthwhile to deal with the rapid addition of the sum to all elements on the segment (also for O (log N)), but this will be too tiring for the person who first understands the segment tree.
A typical example of a problem on a segment tree:
There is a linear array, initially filled with some data. Next come 2 types of requests:
1st type - find the value of the maximum element on the segment of the array [a..b].
2nd type - replace the ith element of the array with x.
The query “add x to all elements on the segment [a..b]” is possible, but in this article I do not consider it.
With the help of a tree of segments, one can search not only for the maximum of numbers, but also for any function satisfying the associativity property.
This limitation is due to the fact that the values ​​are predicted for some segments.
You can also search, for example, not the values, but the sequence numbers of the elements.
It is desirable that the function had a “neutral” argument that does not affect the result. For example, for the sum this number is 0: (a + 0 = a), and for the maximum it is infinity: max (a, -inf) = a.
So let's go.
The easiest (and slowest) way to solve the above problem is to start a linear array, and humbly do what they want from us.
With this implementation, the time to find the answer to the request is of the order O (n). on average, you will have to walk through half of the array to find the maximum. Although there are positive moments - changing the value of an element requires O (1) time. This algorithm can be accelerated by 2 times, if we perform a small pre-calculation: for each pair of elements we find the value of the maximum of them, and write it into another array. Then, when searching for the maximum in the segment, for each pair of elements the value of the larger is already known, and you will only have to compare it. it remains only to carefully check the boundary elements, since the boundary of the requested segment is not necessarily even.
The figure highlights the items that need to be checked.
It is clear that over these arrays you can enter another one, so that the search would be 2 times faster, and over it another one ... and so on until the topmost array will not consist of one element. As it is not difficult to guess, the value of a single element in the topmost array is the value of the maximum element.
')
Some explanations: the number near the top of the tree is the position of this top in the real array. With this implementation of tree storage, it is very convenient to look for the ancestor and descendants of a vertex: the ancestor of the vertex i has the number i / 2, and the descendants of the number i * 2 and i * 2 + 1. The figure shows that it is necessary that the length of the array is a power of two. If this is not the case, then the array can be supplemented with neutral elements at the end. Memory consumption of the storage structure from 2n to 4n, (n - the number of elements).
The search algorithm “from above” (there is also “below”) is very simple both in understanding and implementation (although it may confuse those who are not familiar with recursion).
The algorithm is as follows:
We start the survey from the top 1 (the top one).
1. Let the current vertex know the maximum on the interval l..r.
“The areas [a..b] and [l..r] intersect?”
possible options:
a. do not intersect at all.
so as not to affect the result of the calculation, we will return the neutral element (infinity).
b. the region [l..r] completely lies inside [a..b].
return the calculated value at the current vertex.
with. another way to overlap areas.
ask the same for the children of the current vertex and calculate the maximum among them (see the code if it is not clear).
As you can see, the algorithm is short, but recursive. The time complexity is O (logN), which is much more ray than O (N). for example, with an array of 10 ^ 9 elements, about 32 comparisons are needed.
Changing the number in this structure is even easier - you have to go through all the vertices from the given one to the 1st, and if the value in the current is less than the new, then replace it. It also takes O (log N) time.
The implementation of the algorithm.
It is assumed that the number of elements in the array is no more than 1024 (numbers 0..1023).
#include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // â„– . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }#include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // â„– . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }#include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // â„– . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }#include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // â„– . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }#include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // â„– . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }#include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // â„– . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }#include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // â„– . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }#include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // â„– . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }#include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // â„– . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }#include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // â„– . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }#include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // â„– . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }#include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // â„– . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }#include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // â„– . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }#include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // â„– . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }#include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // â„– . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }#include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // â„– . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }#include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // â„– . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }#include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // â„– . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }#include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // â„– . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }#include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // â„– . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }#include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // â„– . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }#include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // â„– . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }#include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // â„– . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }#include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // â„– . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }#include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // â„– . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }#include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // â„– . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }#include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // â„– . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }#include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // â„– . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }#include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // â„– . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }#include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // â„– . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }#include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // â„– . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }#include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // â„– . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }#include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // â„– . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }#include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // â„– . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }#include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // â„– . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }#include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // â„– . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }#include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // â„– . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }#include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // â„– . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }#include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // â„– . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }#include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // â„– . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }#include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // â„– . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }#include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // â„– . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }#include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // â„– . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }#include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // â„– . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }#include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // â„– . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }#include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // â„– . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }#include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // â„– . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }#include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // â„– . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }#include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // â„– . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }#include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // â„– . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }#include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // â„– . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }#include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // â„– . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }#include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // â„– . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }#include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // â„– . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }#include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // â„– . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }#include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // â„– . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }#include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // â„– . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }#include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // â„– . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }#include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // â„– . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }#include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // â„– . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }#include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // â„– . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }
#include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // â„– . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }
That, in general, is all that is necessary to know first about the segment tree.
For a change, you can still deal with the calculation algorithm “from below” (which, by the way, is non-recursive), although I find it less attractive. Well and, of course, it is worthwhile to deal with the rapid addition of the sum to all elements on the segment (also for O (log N)), but this will be too tiring for the person who first understands the segment tree.
Source: https://habr.com/ru/post/128787/
All Articles