/*
NOTE: some of the classes below are still in developing: nrx_segment_tree, nrx_state_machine
*/
#include <cstdio>
#include <vector>
const int DIM = 1 << 17;
using namespace std;
class nrx_input_reader {
private:
FILE *input_file;
static const int SIZE = 1 << 20;
char *buffer; int cursor, sign;
long long fractional_part;
void advance() {
if( ++cursor == SIZE ) {
cursor = 0;
fread( buffer, SIZE, 1, input_file );
}
return;
}
public:
nrx_input_reader( const char *file_name, const char *file_type ) {
input_file = fopen( file_name, file_type ); cursor = 0;
buffer = new char[SIZE]; fread( buffer, SIZE, 1, input_file );
}
~nrx_input_reader() {
fclose( input_file );
delete buffer;
}
template <class Type>
nrx_input_reader &operator >>( Type &value ) {
value = 0; sign = 1; fractional_part = 10;
while( buffer[cursor] < '0' || buffer[cursor] > '9' ) {
if( buffer[cursor] == '-' )
sign = -1;
advance();
}
while( buffer[cursor] >= '0' && buffer[cursor] <= '9' ) {
value = value * 10 + ( buffer[cursor] - '0' ) * sign;
advance();
}
if( buffer[cursor] == '.' ) {
advance();
while( buffer[cursor] >= '0' && buffer[cursor] <= '9' ) {
value += ( buffer[cursor] - '0' ) * 1.0 * sign / fractional_part;
advance();
}
}
return *this;
}
nrx_input_reader &operator >>( char *string_pos ) {
while( buffer[cursor] == ' ' || buffer[cursor] == '\n' )
advance();
while( buffer[cursor] != ' ' && buffer[cursor] != '\n' ) {
*string_pos = buffer[cursor]; string_pos ++;
advance();
}
return *this;
}
};
template <typename Type>
Type nrx_max( Type A, Type B ) {
return A > B ? A : B;
}
template <typename Type>
Type nrx_min( Type A, Type B ) {
return A < B ? A : B;
}
template <typename Type>
void nrx_swap( Type &A, Type &B ) {
Type C = A; A = B; B = C;
return;
}
template <typename Type>
void nrx_memset( Type *start_pos, Type *finish_pos, Type value ) {
for( Type *cursor = start_pos; cursor != finish_pos; cursor ++ )
*cursor = value;
return;
}
template <typename Type>
void nrx_reverse( Type *start_pos, Type *finish_pos ) {
for( Type *index1 = start_pos, *index2 = finish_pos - 1; index1 < index2; index1 ++, index2 -- )
nrx_swap( *index1, *index2 );
return;
}
template <typename Type>
void nrx_memcpy( Type *start_pos, Type *finish_pos, Type *index ) {
for( Type *cursor = start_pos; cursor != finish_pos; cursor ++ ) {
*index = *cursor;
index ++; cursor ++;
}
return;
}
template <class Type>
class nrx_vector {
private:
int SIZE = 1, AUX_SIZE, cursor = 0;
Type *my_vector = new Type[SIZE];
Type *my_aux_vector;
void double_the_size() {
AUX_SIZE = SIZE * 2;
my_aux_vector = new Type[AUX_SIZE];
for( int i = 0; i < AUX_SIZE; i ++ ) {
if( i < SIZE )
my_aux_vector[i] = my_vector[i];
else
my_aux_vector[i] = NULL;
}
nrx_swap( my_vector, my_aux_vector );
delete my_aux_vector; SIZE = AUX_SIZE;
return;
}
public:
nrx_vector( int SIZE ) {
my_vector = new Type[SIZE];
for( int i = 0; i < SIZE; i ++ )
my_vector[i] = NULL;
}
Type &operator []( int position ) {
return my_vector[position];
}
void push_back( Type value ) {
if( cursor == SIZE )
double_the_size();
my_vector[cursor++] = value;
}
void clear() {
AUX_SIZE = 1;
my_aux_vector = new Type[AUX_SIZE];
my_aux_vector[0] = NULL;
nrx_swap( my_vector, my_aux_vector );
delete my_aux_vector;
return;
}
void resize( int AUX_SIZE ) {
my_aux_vector = new Type[AUX_SIZE];
for( int i = 0; i < AUX_SIZE; i ++ ) {
if( i < SIZE )
my_aux_vector[i] = my_vector[i];
else
my_aux_vector[i] = NULL;
}
swap( my_vector, my_aux_vector );
delete my_aux_vector;
return;
}
Type begin() { return my_vector; }
Type end() { return my_vector + cursor; }
void pop_back() { my_vector[--cursor] = NULL; return; }
int size() { return cursor; }
};
template <class Type>
class nrx_queue {
private:
int SIZE = 0;
struct queue_element {
Type value; queue_element *next;
queue_element() {
value = NULL;
next = NULL;
}
} *first_element, *last_element;
public:
void push_back( Type value ) {
queue_element *aux_value = new queue_element;
aux_value -> value = value;
if( SIZE == 0 ) {
first_element = aux_value;
last_element = aux_value;
} else {
last_element -> next = aux_value;
last_element = last_element -> next;
}
SIZE ++;
return;
}
void pop_front() {
queue_element *aux_value = first_element;
first_element = first_element -> next;
SIZE --;
delete aux_value;
return;
}
void clear() {
while( SIZE )
pop_front();
return;
}
Type front() { return first_element -> value; }
Type back() { return last_element -> value; }
bool empty() { return SIZE > 0; }
};
template <class Type>
class nrx_deque {
private:
int SIZE = 0;
struct deque_element {
Type value; deque_element *next, *last;
deque_element() {
value = NULL;
next = NULL;
last = NULL;
}
} *first_element, *last_element;
public:
void push_back( Type value ) {
deque_element *aux_value = new deque_element;
aux_value -> value = value;
if( SIZE == 0 ) {
first_element = aux_value;
last_element = aux_value;
} else {
last_element -> next = aux_value;
aux_value -> last = last_element;
last_element = last_element -> next;
}
SIZE ++;
return;
}
void push_front( Type &value ) {
deque_element *aux_value = new deque_element;
aux_value -> value = value;
if( SIZE == 0 ) {
first_element = aux_value;
last_element = aux_value;
} else {
first_element -> last = aux_value;
aux_value -> next = first_element;
first_element = first_element -> last;
}
SIZE ++;
return;
}
void pop_back() {
deque_element *aux_value = last_element;
last_element = last_element -> last;
SIZE --;
delete aux_value;
return;
}
void pop_front() {
deque_element *aux_value = first_element;
first_element = first_element -> next;
SIZE --;
delete aux_value;
return;
}
void clear() {
while( SIZE )
pop_front();
return;
}
Type front() { return first_element -> value; }
Type back() { return last_element -> value; }
bool empty() { return SIZE > 0; }
};
class nrx_state_machine {
private:
static const int SIGMA = 26;
struct trie {
int cnt_words;
int cnt_children;
int cnt_occurrences;
trie *back_node;
trie *children[SIGMA];
vector <trie *> front_node; // NU MERGE NRX_VECTOR !!!
trie() {
cnt_words = NULL;
cnt_children = NULL;
cnt_occurrences = NULL;
back_node = NULL;
for( int i = 0; i < SIGMA; i ++ )
children[i] = NULL;
front_node.clear();
}
} *root = new trie;
void insert_word( trie *node, char *my_string ) {
if( *my_string == NULL ) {
node -> cnt_words ++;
return;
}
if( node -> children[*my_string - 'a'] == NULL ) {
node -> children[*my_string - 'a'] = new trie;
node -> cnt_children ++;
}
insert_word( node -> children[*my_string - 'a'], my_string + 1 );
return;
}
bool delete_word( trie *node, char *my_string ) {
if( *my_string == NULL ) node -> cnt_words --; else
if( delete_word( node -> children[*my_string - 'a'], my_string + 1) )
node -> cnt_children --;
if( node != root && node -> cnt_children == NULL && node -> cnt_words == NULL ) {
delete node;
return 1;
}
return 0;
}
int count_word( trie *node, char *my_string ) {
if( *my_string == NULL )
return node -> cnt_words;
if( node -> children[*my_string - 'a'] != NULL )
return count_word( node -> children[*my_string - 'a'], my_string + 1 );
return 0;
}
int longest_prefix( trie *node, char *my_string, int prefix_length ) {
if( *my_string == NULL )
return prefix_length;
if( node -> children[*my_string - 'a'] != NULL )
return longest_prefix( node -> children[*my_string - 'a'], my_string + 1, prefix_length + 1 );
return prefix_length;
}
void reset_machine( trie *node ) {
node -> back_node = NULL;
node -> cnt_occurrences = NULL;
node -> front_node.clear();
for( int i = 0; i < SIGMA; i ++ )
if( node -> children[i] != NULL )
reset_machine( node -> children[i] );
return;
}
void build_back_edges( trie *start_node ) {
nrx_queue<trie *> my_queue;
my_queue.push_back( start_node );
while( !my_queue.empty() ) {
trie *node = my_queue.front();
for( int i = 0; i < SIGMA; i ++ ) {
if( node -> children[i] != NULL ) {
trie *aux_node = node -> back_node;
while( aux_node && aux_node -> children[i] == NULL )
aux_node = aux_node -> back_node;
if( aux_node == NULL )
node -> children[i] -> back_node = root;
else
node -> children[i] -> back_node = aux_node -> children[i];
node -> children[i] -> front_node.push_back( node -> children[i] );
my_queue.push_back( node -> children[i] );
}
}
my_queue.pop_front();
}
return;
}
void build_occurrences( trie *node, char *my_string ) {
if( *my_string == NULL )
return;
while( node != root && node -> children[*my_string - 'a'] == NULL )
node = node -> back_node;
if( node -> children[*my_string - 'a'] != NULL )
node = node -> children[*my_string - 'a'];
node -> cnt_occurrences ++;
build_occurrences( node, my_string + 1 );
return;
}
void build_partial_sum( trie *node ) {
for( int i = 0; i < node -> front_node.size(); i ++ ) {
build_partial_sum( node -> front_node[i] );
node -> cnt_occurrences += node -> front_node[i] -> cnt_occurrences;
}
return;
}
int count_occurrences( trie *node, char *my_string ) {
if( *my_string == NULL )
return node -> cnt_occurrences;
if( node -> children[*my_string - 'a'] != NULL )
return count_occurrences( node -> children[*my_string - 'a'], my_string + 1 );
return 0;
}
public:
void insert_word( char *my_string ) {
insert_word( root, my_string );
return;
}
void delete_word( char *my_string ) {
delete_word( root, my_string );
return;
}
int count_word( char *my_string ) {
return count_word( root, my_string );
}
int longest_prefix( char *my_string ) {
return longest_prefix( root, my_string, 0 );
}
void build_occurrences( char *my_string ) {
reset_machine( root );
build_back_edges( root );
build_occurrences( root, my_string );
build_partial_sum( root );
return;
}
int count_occurrences( char *my_string ) {
return count_occurrences( root, my_string );
}
};
/*
* You can make every operation only with 3 types of numbers:
* 1. integer positive number
* 2. string positive number
* 3. nrx_big_number number
*
* NOTE: don't add / substract a negative number! (YET)
*/
/*
class nrx_big_number {
private:
static const int BASE = 1000000000;
struct nrx_big_number {
int cnt_digits;
nrx_vector<int> number;
};
public:
// Integer number
template <class Type>
nrx_big_number &operator +=( Type second_number ) {
return *this;
}
template <class Type>
nrx_big_number &operator -=( Type second_number ) {
return *this;
}
template <class Type>
nrx_big_number &operator ++( Type second_number ) {
return *this;
}
template <class Type>
nrx_big_number &operator --( Type second_number ) {
return *this;
}
template <class Type>
nrx_big_number &operator *=( Type second_number ) {
return *this;
}
template <class Type>
nrx_big_number &operator /=( Type second_number ) {
return *this;
}
template <class Type>
nrx_big_number &operator %=( Type second_number ) {
return *this;
}
template <class Type>
nrx_big_number &operator ^=( Type second_number ) {
return *this;
}
template <class Type>
nrx_big_number &operator ~=( Type second_number ) {
return *this;
}
template <class Type>
nrx_big_number &operator <<=( Type second_number ) {
return *this;
}
template <class Type>
nrx_big_number &operator >>=( Type second_number ) {
return *this;
}
// String number
nrx_big_number &operator +=( char *string_pos ) {
return *this;
}
nrx_big_number &operator -=( char *string_pos ) {
return *this;
}
nrx_big_number &operator ++( char *string_pos ) {
return *this;
}
nrx_big_number &operator --( char *string_pos ) {
return *this;
}
nrx_big_number &operator *=( char *string_pos ) {
return *this;
}
nrx_big_number &operator /=( char *string_pos ) {
return *this;
}
nrx_big_number &operator %=( char *string_pos ) {
return *this;
}
nrx_big_number &operator ^=( char *string_pos ) {
return *this;
}
nrx_big_number &operator ~=( char *string_pos ) {
return *this;
}
nrx_big_number &operator <<=( char *string_pos ) {
return *this;
}
nrx_big_number &operator >>=( char *string_pos ) {
return *this;
}
// nrx_big_number number
nrx_big_number &operator +=( nrx_big_number &second_number ) {
return *this;
}
nrx_big_number &operator -=( nrx_big_number &second_number ) {
return *this;
}
nrx_big_number &operator ++( nrx_big_number &second_number ) {
return *this;
}
nrx_big_number &operator --( nrx_big_number &second_number ) {
return *this;
}
nrx_big_number &operator *=( nrx_big_number &second_number ) {
return *this;
}
nrx_big_number &operator /=( nrx_big_number &second_number ) {
return *this;
}
nrx_big_number &operator %=( nrx_big_number &second_number ) {
return *this;
}
nrx_big_number &operator ^=( nrx_big_number &second_number ) {
return *this;
}
nrx_big_number &operator ~=( nrx_big_number &second_number ) {
return *this;
}
nrx_big_number &operator <<=( nrx_big_number &second_number ) {
return *this;
}
nrx_big_number &operator >>=( nrx_big_number &second_number ) {
return *this;
}
}; */
template <class Type>
struct nrx_segment_tree {
private:
static const int INF = 0x3f3f3f3f; // TREBUIE MODIFICAT
Type *left_index, *right_index;
struct tree_node {
Type minim, maxim, lazy, sum, type;
tree_node *left_son, *right_son;
tree_node() {
minim = +INF; maxim = -INF;
lazy = sum = type = NULL;
left_son = right_son = NULL;
}
} *root = new tree_node;
void reset_tree( tree_node *node ) {
if( node -> left_son != NULL )
reset_tree( node -> left_son );
if( node -> right_son != NULL )
reset_tree( node -> right_son );
if( node != root )
delete node;
else {
node -> left_son = node -> right_son = NULL; node -> lazy = node -> type = NULL;
node -> minim = +INF; node -> maxim = -INF; node -> sum = NULL;
}
return;
}
void update_lazy( tree_node *node, int left, int right ) {
switch( node -> type ) {
case 1: { // ADD( left, right, lazy )
node -> minim += node -> lazy;
node -> maxim += node -> lazy;
node -> sum += node -> lazy * ( right - left + 1 );
break;
}
case 2: { // MUL( left, right, lazy )
node -> minim *= node -> lazy;
node -> maxim *= node -> lazy;
node -> sum *= node -> lazy;
break;
}
case 3: { // DIV( left, right, lazy )
node -> minim /= node -> lazy;
node -> maxim /= node -> lazy;
node -> sum /= node -> lazy;
break;
}
case 4: { // SET( left, right, lazy )
node -> minim = node -> lazy;
node -> maxim = node -> lazy;
node -> sum = node -> lazy * ( right - left + 1 );
break;
}
}
if( left != right ) {
node -> left_son -> lazy = node -> lazy; node -> left_son -> type = node -> type;
node -> right_son -> lazy = node -> lazy; node -> right_son -> type = node -> type;
}
node -> lazy = node -> type = 0;
return;
}
void update_node( tree_node *node, int left, int right ) {
int middle = left + ( right - left ) / 2;
if( node -> left_son -> lazy != 0 )
update_lazy( node -> left_son, left, middle );
if( node -> right_son -> lazy != 0 )
update_lazy( node -> right_son, middle + 1, right );
node -> minim = nrx_min( node -> left_son -> minim, node -> right_son -> minim );
node -> maxim = nrx_max( node -> left_son -> maxim, node -> right_son -> maxim );
node -> sum = node -> left_son -> sum + node -> right_son -> sum;
return;
}
void build_tree( tree_node *node, int left, int right ) {
if( left > right ) return;
if( left == right ) {
node -> minim = *( left_index + left - 1 );
node -> maxim = *( left_index + left - 1 );
node -> sum = *( left_index + left - 1 );
return;
}
node -> left_son = new tree_node;
node -> right_son = new tree_node;
int middle = left + ( right - left ) / 2;
build_tree( node -> left_son, left, middle );
build_tree( node -> right_son, middle + 1, right );
update_node( node, left, right );
return;
}
void add_value( tree_node *node, int left, int right, int start, int finish, Type value ) {
if( node -> lazy != 0 )
update_lazy( node, left, right );
if( left > right || left > finish || start > right )
return;
if( start <= left && right <= finish ) {
node -> minim += value;
node -> maxim += value;
node -> sum += value * ( right - left + 1 );
if( left != right ) {
node -> left_son -> lazy = node -> left_son -> type != node -> type ? value : node -> left_son -> lazy + value;
node -> right_son -> lazy = node -> right_son -> type != node -> type ? value : node -> right_son -> lazy + value;
node -> left_son -> type = node -> right_son -> type = 1;
}
return;
}
int middle = left + ( right - left ) / 2;
add_value( node -> left_son, left, middle, start, finish, value );
add_value( node -> right_son, middle + 1, right, start, finish, value );
update_node( node, left, right );
return;
}
void mul_value( tree_node *node, int left, int right, int start, int finish, Type value ) {
if( node -> lazy != 0 )
update_lazy( node, left, right );
if( left > right || left > finish || start > right )
return;
if( start <= left && right <= finish ) {
node -> minim *= value;
node -> maxim *= value;
node -> sum *= value;
if( left != right ) {
node -> left_son -> lazy = node -> left_son -> type != node -> type ? value : node -> left_son -> lazy * value;
node -> right_son -> lazy = node -> right_son -> type != node -> type ? value : node -> right_son -> lazy * value;
node -> left_son -> type = node -> right_son -> type = 2;
}
return;
}
int middle = left + ( right - left ) / 2;
mul_value( node -> left_son, left, middle, start, finish, value );
mul_value( node -> right_son, middle + 1, right, start, finish, value );
update_node( node, left, right );
return;
}
void div_value( tree_node *node, int left, int right, int start, int finish, Type value ) {
if( node -> lazy != 0 )
update_lazy( node, left, right );
if( left > right || left > finish || start > right )
return;
if( start <= left && right <= finish ) {
node -> minim *= value;
node -> maxim *= value;
node -> sum *= value;
if( left != right ) {
node -> left_son -> lazy = node -> left_son -> type != node -> type ? value : node -> left_son -> lazy * value;
node -> right_son -> lazy = node -> right_son -> type != node -> type ? value : node -> right_son -> lazy * value;
node -> left_son -> type = node -> right_son -> type = 3;
}
return;
}
int middle = left + ( right - left ) / 2;
div_value( node -> left_son, left, middle, start, finish, value );
div_value( node -> right_son, middle + 1, right, start, finish, value );
update_node( node, left, right );
return;
}
void set_value( tree_node *node, int left, int right, int start, int finish, Type value ) {
if( node -> lazy != 0 )
update_lazy( node, left, right );
if( left > right || left > finish || start > right )
return;
if( start <= left && right <= finish ) {
node -> minim = value;
node -> maxim = value;
node -> sum = value * ( right - left + 1 );
if( left != right ) {
node -> left_son -> lazy = node -> right_son -> lazy = value;
node -> left_son -> type = node -> right_son -> type = 4;
}
return;
}
int middle = left + ( right - left ) / 2;
set_value( node -> left_son, left, middle, start, finish, value );
set_value( node -> right_son, middle + 1, right, start, finish, value );
update_node( node, left, right );
return;
}
Type get_min( tree_node *node, int left, int right, int start, int finish ) {
Type value1, value2, value3; value3 = INF;
if( node -> lazy != 0 )
update_lazy( node, left, right );
if( left > right || left > finish || start > right )
return value3;
if( start <= left && right <= finish )
return node -> minim;
int middle = left + ( right - left ) / 2;
value1 = get_min( node -> left_son, left, middle, start, finish );
value2 = get_min( node -> right_son, middle + 1, right, start, finish );
value3 = nrx_min( value1, value2 );
return value3;
}
Type get_max( tree_node *node, int left, int right, int start, int finish ) {
Type value1, value2, value3; value3 = -INF;
if( node -> lazy != 0 )
update_lazy( node, left, right );
if( left > right || left > finish || start > right )
return value3;
if( start <= left && right <= finish )
return node -> maxim;
int middle = left + ( right - left ) / 2;
value1 = get_max( node -> left_son, left, middle, start, finish );
value2 = get_max( node -> right_son, middle + 1, right, start, finish );
value3 = nrx_max( value1, value2 );
return value3;
}
Type get_sum( tree_node *node, int left, int right, int start, int finish ) {
Type value1, value2, value3; value3 = 0;
if( node -> lazy != 0 )
update_lazy( node, left, right );
if( left > right || left > finish || start > right )
return value3;
if( start <= left && right <= finish )
return node -> sum;
int middle = left + ( right - left ) / 2;
value1 = get_sum( node -> left_son, left, middle, start, finish );
value2 = get_sum( node -> right_son, middle + 1, right, start, finish );
value3 = value1 + value2;
return value3;
}
public:
void build_tree( Type *start_pos, Type *finish_pos ) {
reset_tree( root ); left_index = start_pos; right_index = finish_pos;
build_tree( root, 1, right_index - left_index );
return;
}
void add_value( Type *start_pos, Type *finish_pos, Type value ) {
add_value( root, 1, right_index - left_index, start_pos - left_index + 1, finish_pos - left_index, value );
return;
}
void mul_value( Type *start_pos, Type *finish_pos, Type value ) {
mul_value( root, 1, right_index - left_index, start_pos - left_index + 1, finish_pos - left_index, value );
return;
}
void div_value( Type *start_pos, Type *finish_pos, Type value ) {
div_value( root, 1, right_index - left_index, start_pos - left_index + 1, finish_pos - left_index, value );
return;
}
void set_value( Type *start_pos, Type *finish_pos, Type value ) {
set_value( root, 1, right_index - left_index, start_pos - left_index + 1, finish_pos - left_index, value );
return;
}
Type get_min( Type *start_pos, Type *finish_pos ) {
return get_min( root, 1, right_index - left_index, start_pos - left_index + 1, finish_pos - left_index );
}
Type get_max( Type *start_pos, Type *finish_pos ) {
return get_max( root, 1, right_index - left_index, start_pos - left_index + 1, finish_pos - left_index );
}
Type get_sum( Type *start_pos, Type *finish_pos ) {
return get_sum( root, 1, right_index - left_index, start_pos - left_index + 1, finish_pos - left_index );
}
}; nrx_segment_tree <int> my_segment_tree;
int V[DIM], N, M, K, X, Y;
int main () {
nrx_input_reader input_file( "arbint.in" , "r" );
freopen ("arbint.out","w", stdout);
input_file >> N >> M;
for( int i = 1; i <= N; i ++ )
input_file >> V[i];
my_segment_tree.build_tree( V + 1, V + N + 1 );
for( int i = 1; i <= M; i ++ ) {
input_file >> K >> X >> Y;
switch( K ) {
case 0: {
printf( "%d\n", my_segment_tree.get_max( V + X, V + Y + 1 ) );
break;
}
case 1: {
my_segment_tree.set_value( V + X, V + X + 1, Y );
break;
}
}
}
return 0;
}
Emanuel Nrx StarGold2