Cod sursa(job #2558951)

Utilizator TheoryCraft_Alexandru Duma TheoryCraft_ Data 26 februarie 2020 21:38:44
Problema Arbori de intervale Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 7.63 kb
// Infoarena-arbint.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <iostream>
#include <vector>
#include <memory>
#include <fstream>
#include <algorithm>

struct MaximumIntervalTreeInternal
{
    int max = 0;
    int leftIdx = 0;
    int rightIdx = 0;
    std::shared_ptr<MaximumIntervalTreeInternal> left;
    std::shared_ptr<MaximumIntervalTreeInternal> right;
};

void updateMax(std::shared_ptr<MaximumIntervalTreeInternal> root)
{
    if (!root->left && !root->right)
    {
        return;
    }
    if (!root->left)
    {
        root->max = root->right->max;
    }
    else if (!root->right)
    {
        root->max = root->left->max;
    }
    else
    {
        root->max = root->left->max > root->right->max ? root->left->max : root->right->max;
    }
}

std::shared_ptr<MaximumIntervalTreeInternal> buildInternalTreeRec(const std::vector<int>& BackingArray, int Left, int Right)
{
    auto root = std::make_shared<MaximumIntervalTreeInternal>();
    root->leftIdx = Left;
    root->rightIdx = Right;

    if (Left == Right)
    {
        root->max = BackingArray[Left];
        return root;
    }

    int mid = (Right + Left) / 2;
    root->left = buildInternalTreeRec(BackingArray, Left, mid);
    root->right = buildInternalTreeRec(BackingArray, mid + 1, Right);
    updateMax(root);
    return root;
}

std::shared_ptr<MaximumIntervalTreeInternal> buildInternalTree(const std::vector<int>& BackingArray)
{
    return buildInternalTreeRec(BackingArray, 0, BackingArray.size() - 1);
}

void updateValue(std::shared_ptr<MaximumIntervalTreeInternal> Root, int NewValue, int Index)
{
    if (Root->leftIdx == Root->rightIdx && Root->leftIdx == Index)
    {
        Root->max = NewValue;
        return;
    }

    int mid = (Root->rightIdx + Root->leftIdx) / 2;
    if (Index <= mid && Root->left)
    {
        updateValue(Root->left, NewValue, Index);
    }
    else if(Index > mid && Root->right)
    {
        updateValue(Root->right, NewValue, Index);
    }
    updateMax(Root);
}

int getMaximum(std::shared_ptr<MaximumIntervalTreeInternal> root, int Left, int Right)
{
    if (Left == root->leftIdx && Right == root->rightIdx)
    {
        return root->max;
    }

    int mid = (root->leftIdx + root->rightIdx) / 2;
    if (Left <= mid && Right <= mid)
    {
        return getMaximum(root->left, Left, Right);
    }
    else if (Left > mid && Right > mid)
    {
        return getMaximum(root->right, Left, Right);
    }
    else
    {
        return std::max(getMaximum(root->left, Left, mid), getMaximum(root->right, mid + 1, Right));
    }
}

int getLeftIdx(int NodeIdx)
{
    return (NodeIdx * 2) + 1;
}

int getRightIdx(int NodeIdx)
{
    return (NodeIdx * 2) + 2;
}

int getLeftValue(std::vector<int>& TreeVector, int NodeIdx)
{
    return TreeVector[getLeftIdx(NodeIdx)];
}

int getRightValue(std::vector<int>& TreeVector, int NodeIdx)
{
    return TreeVector[getRightIdx(NodeIdx)];
}

void updateTreeValue(std::vector<int>& TreeVector, int NodeIdx, int Left, int Right, int Idx, int NewValue)
{
    if (Left == Right && Left == Idx)
    {
        TreeVector[NodeIdx] = NewValue;
        return;
    }

    int mid = (Left + Right) / 2;
    if (Idx <= mid && getLeftIdx(NodeIdx) < TreeVector.size())
    {
        updateTreeValue(TreeVector, getLeftIdx(NodeIdx), Left, mid, Idx, NewValue);
    }
    else if(Idx > mid && getRightIdx(NodeIdx) < TreeVector.size())
    {
        updateTreeValue(TreeVector, getRightIdx(NodeIdx), mid + 1, Right, Idx, NewValue);
    }
    TreeVector[NodeIdx] = std::max(getLeftValue(TreeVector, NodeIdx), getRightValue(TreeVector, NodeIdx));
}

int getMaxValue(std::vector<int>& TreeVector, int NodeIdx, int NodeLeft, int NodeRight, int TargetLeft, int TargetRight)
{
    if (NodeLeft == TargetLeft && NodeRight == TargetRight)
    {
        return TreeVector[NodeIdx];
    }

    int mid = (NodeLeft + NodeRight) / 2;
    if (TargetLeft <= mid && TargetRight <= mid)
    {
        return getMaxValue(TreeVector, getLeftIdx(NodeIdx), NodeLeft, mid, TargetLeft, TargetRight);
    }
    else if (TargetLeft > mid && TargetRight > mid)
    {
        return getMaxValue(TreeVector, getRightIdx(NodeIdx), mid + 1, NodeRight, TargetLeft, TargetRight);
    }
    else
    {
        return std::max(getMaxValue(TreeVector, getLeftIdx(NodeIdx), NodeLeft, mid, TargetLeft, mid),
            getMaxValue(TreeVector, getRightIdx(NodeIdx), mid + 1, NodeRight, mid + 1, TargetRight));
    }
}

void buildTreeRec(std::vector<int>& TreeVector, const std::vector<int> BackingArray, int TreeNode, int Left, int Right)
{
    if (Left == Right)
    {
        TreeVector[TreeNode] = BackingArray[Left];
        return;
    }

    int mid = (Right + Left) / 2;
    buildTreeRec(TreeVector, BackingArray, (TreeNode * 2) + 1, Left, mid);
    buildTreeRec(TreeVector, BackingArray, (TreeNode * 2) + 2, mid + 1, Right);
    TreeVector[TreeNode] = std::max(TreeVector[(TreeNode * 2) + 1], TreeVector[(TreeNode * 2) + 2]);
}

std::vector<int> buildTree(const std::vector<int>& BackingArray)
{
    std::vector<int> treeVector((2 * BackingArray.size()) - 1);
    buildTreeRec(treeVector, BackingArray, 0, 0, BackingArray.size() - 1);
    return treeVector;
}

class MaximumIntervalTree
{
public:
    MaximumIntervalTree(const std::vector<int>& BackingArray)
        : treeVector{buildTree(BackingArray)},
        lastIdx{BackingArray.size() - 1}
    {}

    int maxInRange(int Left, int Right)
    {
        return getMaxValue(treeVector, 0, 0, lastIdx, Left, Right);
    }

    void updateMax(int NewValue, int Index)
    {
        updateTreeValue(treeVector, 0, 0, lastIdx, Index, NewValue);
    }

private:
    //std::shared_ptr<MaximumIntervalTreeInternal> root;
    std::vector<int> treeVector;
    size_t lastIdx;
};

std::vector<int> readBackingArray(std::istream& in, int n)
{
    std::vector<int> arr(n, 0);
    for (int i = 0; i < n; ++i)
    {
        in >> arr[i];
    }
    return arr;
}

void processInput(std::istream& in, std::ostream& out, MaximumIntervalTree& Tree, int CommandCount)
{
    while (CommandCount--)
    {
        int command;
        in >> command;
        switch (command)
        {
        case 0:
            int left, right;
            in >> left >> right;
            out << Tree.maxInRange(--left, --right) << std::endl;
            break;
        case 1:
            int index, newValue;
            in >> index >> newValue;
            Tree.updateMax(newValue, --index);
            break;
        }
    }
}

int main()
{
    std::ifstream in("arbint.in");
    std::ofstream out("arbint.out");
    int arrSize, commandsCount;
    in >> arrSize >> commandsCount;
    auto backingArray = readBackingArray(in, arrSize);
    MaximumIntervalTree tree{ backingArray };
    
    processInput(in, out, tree, commandsCount);
    //processInput(in, std::cout, tree, commandsCount);
    return 0;
}

// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
// Debug program: F5 or Debug > Start Debugging menu

// Tips for Getting Started: 
//   1. Use the Solution Explorer window to add/manage files
//   2. Use the Team Explorer window to connect to source control
//   3. Use the Output window to see build output and other messages
//   4. Use the Error List window to view errors
//   5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
//   6. In the future, to open this project again, go to File > Open > Project and select the .sln file