Cod sursa(job #2600416)

Utilizator GabiTulbaGabi Tulba-Lecu GabiTulba Data 12 aprilie 2020 16:00:45
Problema Arbori de intervale Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.54 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>


typedef struct _Tree {
    struct _Tree *left_son, *right_son;
    int info;
}Tree;

int max(int a, int b) {
    return a > b ? a : b;
}

void Merge_Sons(Tree *T, Tree *left, Tree *right) {
    T->info = max(left->info, right->info);
}

Tree* Init_Node() {
    Tree *T = (Tree *) malloc(sizeof(Tree));
    T->left_son = T->right_son = NULL;

    return T;
}

void Init(Tree *T, int *v, int left, int right) {
    if(left == right) {
        T->info = v[left];
    } else {
        int middle = (left + right) / 2;

        T->left_son = Init_Node();
        T->right_son = Init_Node();

        Init(T->left_son, v, left, middle);
        Init(T->right_son, v, middle + 1, right);

        Merge_Sons(T, T->left_son, T->right_son);
    }
}

void Update(Tree *T, int pos, int value, int left, int right) {
    if(left == right) {
        T->info = value;
    } else {
        int middle = (left + right) / 2;

        if(pos <= middle)
            Update(T->left_son, pos, value, left, middle);
        else
            Update(T->right_son, pos, value, middle + 1, right);

        Merge_Sons(T, T->left_son, T->right_son);
    }
}

int Query(Tree *T, int left_query, int right_query, int left, int right) {
    if(left_query <= left && right <= right_query) {
        return T->info;
    } else {
        int middle = (left + right) / 2;
        int Max = -1;
        if(left_query <= middle)
            Max= max(Max, Query(T->left_son, left_query, right_query, left, middle));
        else
            Max= max(Max, Query(T->right_son, left_query, right_query, middle + 1, right));
        return Max;
    }
}

void Free(Tree *T) {
    if(T->left_son != NULL) {
        Free(T->left_son);
    }
    if(T->right_son != NULL) {
        Free(T->right_son);
    }
    free(T);
}

int main()
{
    FILE *input = fopen("arbint.in", "r");
    FILE *output = fopen("arbint.out", "w");
    int N, M, type, a, b, *v;
    Tree *T = Init_Node();

    fscanf(input, "%d %d", &N, &M);

    v = (int *) malloc((N + 1) * sizeof(int));
    for(int i = 1; i <= N; i++) {
        fscanf(input, "%d", &v[i]);
    }

    Init(T, v, 1, N);

    for(int i = 1; i <= M; i++) {
        fscanf(input, "%d %d %d", &type, &a, &b);
        if(type == 1) {
            Update(T, a, b, 1, N);
        } else {
            fprintf(output, "%d\n", Query(T, a, b, 1, N));
        }
    }

    Free(T);
    fclose(input);
    fclose(output);

    return 0;
}