लाइन का पेड़

मैं खंडों के पेड़ नामक एक संरचना के बारे में बात करूंगा और सी ++ में इसका सरल कार्यान्वयन दूंगा। यह संरचना उन मामलों में बहुत उपयोगी है जहां एक रैखिक सरणी के खंडों पर एक फ़ंक्शन के मूल्य की खोज करना अक्सर आवश्यक होता है और लगातार तत्वों के समूह के मूल्यों को जल्दी से बदलने में सक्षम होता है।
खंडों के वृक्ष पर कार्य का एक विशिष्ट उदाहरण:
एक रैखिक सरणी है, शुरू में कुछ डेटा से भरा हुआ है। अगला प्रश्न 2 प्रकार के आते हैं:
प्रथम प्रकार - सरणी [a..b] के खंड पर अधिकतम तत्व का मान ज्ञात करें।
2 प्रकार - एक्स के साथ i-th तत्व की जगह x।
क्वेरी "सेगमेंट पर सभी तत्वों को जोड़ने के लिए [a.b]" संभव है, लेकिन इस लेख में मैं इस पर विचार नहीं करूंगा।
सेगमेंट के पेड़ का उपयोग करके, आप न केवल अधिकतम संख्याओं के लिए खोज कर सकते हैं, बल्कि किसी भी फ़ंक्शन के लिए संबद्धता संपत्ति को संतुष्ट कर सकते हैं।

यह सीमा इस तथ्य के कारण है कि कुछ खंडों के लिए मूल्यों की गणना का उपयोग किया जाता है।

आप उदाहरण के लिए, मानों को नहीं, बल्कि तत्वों की क्रम संख्या को भी खोज सकते हैं।
यह वांछनीय है कि फ़ंक्शन में "तटस्थ" तर्क है, जो परिणाम को प्रभावित नहीं करता है। उदाहरण के लिए, इस राशि के लिए यह संख्या 0: (a + 0 = a) है, और अधिकतम के लिए यह अनंत है: अधिकतम (एक -inf) = एक।
तो चलिए चलते हैं।
उपरोक्त समस्या को हल करने का सबसे आसान (और सबसे धीमा) तरीका एक रैखिक सरणी प्राप्त करना है, और कर्तव्यनिष्ठता से वही करना है जो वे हमसे चाहते हैं।
इस तरह के कार्यान्वयन के साथ, अनुरोध का जवाब खोजने में लगने वाला समय O (n) है। औसतन, आपको अधिकतम खोजने के लिए आधे से गुजरना होगा। हालांकि सकारात्मक पहलू हैं - किसी तत्व के मूल्य को बदलने के लिए ओ (1) समय की आवश्यकता होती है। यदि आप एक छोटी गणना करते हैं तो यह एल्गोरिथ्म 2 गुना तेज हो सकता है: प्रत्येक जोड़ी तत्वों के लिए हम उनमें से अधिकतम का मान पाते हैं, और इसे दूसरे सरणी में लिखते हैं। फिर, जब एक खंड में अधिकतम की खोज की जाती है, तो प्रत्येक जोड़ी तत्वों के लिए एक बड़े का मूल्य पहले से ही ज्ञात होता है, और आपको केवल इसकी तुलना करनी होगी। यह केवल सीमा तत्वों की सावधानीपूर्वक जांच करने के लिए बनी हुई है, क्योंकि अनुरोधित खंड की सीमा आवश्यक रूप से भी नहीं है।
आंकड़ा उन तत्वों को उजागर करता है जिन्हें जांचने की आवश्यकता है।



यह स्पष्ट है कि कोई व्यक्ति इन सरणियों पर एक और एक दर्ज कर सकता है ताकि खोज 2 गुना तेज हो, और एक अन्य उस पर ... और इसी तरह जब तक सबसे ऊपरी सरणी में एक तत्व न हो। जैसा कि आप अनुमान लगा सकते हैं, ऊपरवाले सरणी में किसी एक तत्व का मान अधिकतम तत्व का मान है।



कुछ स्पष्टीकरण: पेड़ के शीर्ष के बगल में संख्या एक वास्तविक सरणी में इस शीर्ष की स्थिति है। पेड़ के भंडारण के इस कार्यान्वयन के साथ, शीर्ष के पूर्वज और वंशज की खोज करना बहुत सुविधाजनक है: शीर्ष के पूर्वज के पास संख्या i / 2 है, और संख्या के वंशज i * 2 और i 2 + 1 हैं। यह आंकड़ा से देखा जा सकता है कि यह आवश्यक है कि सरणी की लंबाई दो की शक्ति हो। यदि ऐसा नहीं है, तो सरणी को अंत में तटस्थ तत्वों के साथ पूरक किया जा सकता है। संरचना के भंडारण के लिए मेमोरी की खपत 2 एन से 4 एन तक है, (एन तत्वों की संख्या है)।
खोज एल्गोरिथ्म "ऊपर से" (नीचे "भी है") समझने और कार्यान्वयन में बहुत सरल है (हालांकि उन लोगों के लिए जो पुनरावृत्ति से परिचित नहीं हैं, यह सब कुछ पहेली हो सकता है)।
एल्गोरिथ्म इस प्रकार है:
हम शीर्ष 1 (सबसे ऊपर) से सर्वेक्षण शुरू करते हैं।
1. बता दें कि वर्टिकल इंटरवल के अंतराल में अधिकतम पता होता है l..r।
"इन्टरसेक्ट क्षेत्रों [a..b] और [l..r]?"
संभावित विकल्प:
एक। अंतरंग मत करो।
इसलिए गणना के परिणाम को प्रभावित नहीं करने के लिए, हम तटस्थ तत्व (-इनफिनिटी) को वापस करते हैं।
ख। क्षेत्र [l..r] पूरी तरह से अंदर [a] है।
वर्तमान शीर्ष पर परिकलित मान लौटाएं।
एक। अतिव्यापी क्षेत्रों के लिए एक और विकल्प।
वर्तमान वर्टेक्स के बच्चों से भी यही पूछें और उनमें से अधिकतम की गणना करें (कोड देखें, यदि यह स्पष्ट नहीं है)।

जैसा कि आप देख सकते हैं, एल्गोरिथ्म छोटा है, लेकिन पुनरावर्ती है। समय जटिलता O (logN) है, जो O (N) से बहुत बेहतर है। उदाहरण के लिए, 10 ^ 9 तत्वों की एक सरणी के साथ, लगभग 32 तुलना की आवश्यकता होती है।
इस संरचना में संख्या को बदलना और भी आसान है - आपको दिए गए 1 से सभी कोने से गुजरना होगा, और यदि वर्तमान में मूल्य नए से कम है, तो इसे प्रतिस्थापित करें। इसमें O (log N) समय भी लगता है।
एल्गोरिथ्म का कार्यान्वयन।
यह माना जाता है कि सरणी में तत्वों की संख्या 1024 (संख्या 0..1023) से अधिक नहीं है।

1. #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 ) ; } } }

2. #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 ) ; } } }

4. #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 ) ; } } }

5. #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 ) ; } } }

7. #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 ) ; } } }

8. #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 ) ; } } }

10. #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 ) ; } } }

11. #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 ) ; } } }

12. #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 ) ; } } }

13. #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 ) ; } } }

14. #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 ) ; } } }

15. #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 ) ; } } }

16. #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 ) ; } } }

17. #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 ) ; } } }

18. #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 ) ; } } }

19. #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 ) ; } } }

20. #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 ) ; } } }

21. #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 ) ; } } }

22. #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 ) ; } } }

24. #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 ) ; } } }

25. #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 ) ; } } }

26. #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 ) ; } } }

27. #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 ) ; } } }

28. #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 ) ; } } }

30. #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 ) ; } } }

31. #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 ) ; } } }

32. #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 ) ; } } }

33. #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 ) ; } } }

34. #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 ) ; } } }

35. #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 ) ; } } }

36. #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 ) ; } } }

37. #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 ) ; } } }

38. #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 ) ; } } }

39. #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 ) ; } } }

40. #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 ) ; } } }

41. #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 ) ; } } }

43. #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 ) ; } } }

44. #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 ) ; } } }

45. #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 ) ; } } }

46. #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 ) ; } } }

47. #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 ) ; } } }

48. #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 ) ; } } }

50. #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 ) ; } } }

51. #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 ) ; } } }

52. #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 ) ; } } }

53. #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 ) ; } } }

54. #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 ) ; } } }

55. #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 ) ; } } }

56. #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 ) ; } } }

57. #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 ) ; } } }

58. #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 ) ; } } }

59. #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 ) ; } } }

60. #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 ) ; } } }

61. #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 ) ; } } }

62. #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 ) ; } } }

63. #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 ) ; } } }

64. #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 ) ; } } }

65. #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 ) ; } } }

66. #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 ) ; } } }

67. #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 ) ; } } }

68. #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 ) ; } } }


यहां, सामान्य रूप से, और सब कुछ जो कि आवश्यक है सबसे पहले खंडों के एक पेड़ के बारे में जानना चाहिए।
एक बदलाव के लिए, आप अभी भी नीचे-ऊपर गणना एल्गोरिथ्म का पता लगा सकते हैं (जो संयोगवश, गैर-पुनरावर्ती है), हालांकि मुझे यह कम आकर्षक लगता है। ठीक है, निश्चित रूप से, एक सेगमेंट (ओ (लॉग एन) से परे) पर सभी तत्वों को राशि के त्वरित जोड़ से निपटने के लिए यह सार्थक है, लेकिन यह उस व्यक्ति के लिए बहुत थकाने वाला होगा जो पहले सेगमेंट के पेड़ से निपटता है।