-
Notifications
You must be signed in to change notification settings - Fork 1
/
FASTMAX.cpp
executable file
·113 lines (88 loc) · 1.97 KB
/
FASTMAX.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <string>
#include <algorithm>
#define FOR(i,a,b) for(long long i = a ; i < b ; ++i )
#define PB push_back
using namespace std;
struct Element{
int a;
int b;
int max;
Element* parent;
Element* right;
Element* left;
};
Element * buildTree(Element* parent, int a , int b ){
Element * v= new Element;
v->a = a;
v->b = b;
v->parent = parent;
v->max = 0 ;
if( a != b ){
int middle = (a+b)/2;
v->left = buildTree( v, a, middle );
v->right = buildTree( v, middle + 1, b );
}
else
v->right = v->left = nullptr;
return v;
}
void check( Element * e ){
if( e->max != max( e->right->max , e->left->max ) ){
int rmax = e->right != nullptr ? e->right->max : 0;
int lmax = e->left != nullptr ? e->left->max : 0;
e->max = max( rmax, lmax );
if( e-> parent != nullptr )
check( e->parent );
}
}
void actualize( Element * element , int start, int value ){
if( element->a == start and element-> b == start ){
element->max = value;
check( element->parent );
}
else{
if( start <= element->left->b )
actualize( element->left, start, value );
else
actualize( element->right , start, value );
}
}
int findMax( Element * e , int a, int b ){
int maxl = 0 ;
int maxr = 0;
int middle = ( e->a + e->b )/2;
if(( e->a == a and e->b == b ) or ( e->a == e->b ) )
return e->max;
if( b <= middle )
return findMax( e->left ,a , b);
if( a > middle )
return findMax( e->right, a, b);
maxl = findMax( e->left, a , middle );
maxr = findMax( e->right, middle+1 , b );
return max(maxl, maxr);
}
int main(){
int n;
int m;
int start;
int stop;
int rodzaj;
ios_base::sync_with_stdio( false );
scanf( "%d %d",&n,&m);
Element* tree = buildTree( nullptr, 0, n );
FOR( i , 0 , m ){
scanf( "%d %d %d",&rodzaj,&start,&stop);
if( rodzaj == 1 ){
actualize( tree, start, stop );
}
else{
printf("%d\n" findMax( tree, start, stop ));
}
}
return 0 ;
}