e-olymp 2906. Can you answer these queries — 1

You are given an integer sequence.

[latex]a_1, a_2, \ldots, a_n (|a_i| \le 15007, 1 \le n \le 50000)[/latex].

A query is defined as follows:

[latex]Query(x, y) = MAX (a_i + a_{i+1} + \ldots + a_j, x \le i \le j \le y)[/latex]

Given [latex]m[/latex] queries, your program must output the results of these queries.

Input

The first line contains the integer [latex]n[/latex]. In the second line [latex]n[/latex] integers of the sequence are given. The third line contains the integer [latex]m[/latex]. Then [latex]m[/latex] lines follow, where line [latex]i[/latex] contains two numbers [latex]x_i[/latex] and [latex]y_i[/latex].

Output

Print the results of the [latex]m[/latex] queries, one query per line.

Tests

№	Input	Output
1	3 -1 2 3 1 1 2	2
2	5 1 2 3 4 5 1 1 5	15
3	5 -1 -2 -3 -4 -5 1 1 5	-1
4	8 1 2 -3 -2 10 1 -15 7 4 1 1 3 4 3 6 1 8	1 -2 11 11
5	9 1 -2 3 -4 5 -6 7 -8 9 3 1 9 2 8 2 4	9 7 3

Algorithm

After analyzing the condition of the problem, we can understand that we need on a given segments of array to find subsegment with a maximum amount. We can solve this task by using segment tree, but before this we should modify it a bit. Create a structure of which our tree consists:

struct Node {
    int answer;         
    int sumOnPrefix;
    int sumOnSuffix;
    int sumOnSegment;
}

struct Node {

int answer;

int sumOnPrefix;

int sumOnSuffix;

int sumOnSegment;

}

That is, in each vertex of tree we store [latex]4[/latex] values:

the answer to the task for the current subsegment
the maximum amount among all prefixes
the maximum amount among all suffixes
the sum on the segment

First we need to get the values in the leaves. It’s simple enough all [latex]4[/latex] fields take the value of the number, that corresponds to this leaf. Now, having values in the leaves, we need to learn how to get the values in parent. For this we use the function Node mergeNodes(Node leftChild, Node rightChild), which assign to parent’s fields such values:

Answer in the parent equal to the answer in the right or the left child (means that the best subsegment of the current node is entirely in the left or right child), or the maximum amount of the maximum suffix in the left child and the maximum prefix in the right child (which means that it is partially is in the left child and partially is in the right child).
The maximum amount of the parent on prefix is equal to the maximum prefix of left child or sum on segment of left child and maximum prefix of right child.
The maximum amount of the parent on suffix is equal to the maximum suffix of right child or sum on segment of right child and maximum suffix of right child.
Amount on segment of the parent is equal to the sum on segment of left child and sum on segment of right child.

Now, with all the auxiliary functions for working with a built data structure, we need only to construct a tree and learn to get an answer on it.
We need two more functions:

void build(int *base, Node *tree, int currentNode, int left, int right) — recursive construction of a tree from the leaves to the root by initial sequence numbers.
Node answer(Node *tree, int currentNode, int left, int right, int leftBorder, int rightBorder) — as in the usual tree segments we get an answer going down by the tree, but instead of any associative function (eg sum or maximum) we execute the merger of nodes described earlier. Resulting node will store an answer corresponding to a given in the query segment.

Rest details of the implementation can be found in the code of the program or in the sources of information listed at the end of the article.

Code

#include <cmath>
#include <iostream>
#define INF -15008
using namespace std;

//  Function, that teturn lowest power of 2, bigger than a given number
int lowestBiggerPowOf2Than(int number) {                    
    int answer;
    answer = 1 << (int)(log2((double)number - 1) + 1);
    return answer;
}

//  The structure describing the components from which consists a tree
struct Node {
    int answer;         
    int sumOnPrefix;
    int sumOnSuffix;
    int sumOnSegment;
    //  Empty node takes the value less by 1 than what we can get, because we are looking for maximum subsegment
    Node() {
        answer = INF;
        sumOnPrefix = INF;
        sumOnSuffix = INF;
        sumOnSegment = INF;
    }
    // Constructs a node by a value of the initial sequence of numbers
    Node(int value) {
        answer = value;
        sumOnPrefix = value;
        sumOnSuffix = value;
        sumOnSegment = value;
    }
};

//  Function, that merges two nodes (childs) and returns new node (parent)
Node mergeNodes(Node leftChild, Node rightChild) {
    Node crossedNode;
    crossedNode.sumOnSegment = leftChild.sumOnSegment + rightChild.sumOnSegment;
    crossedNode.sumOnPrefix = max(leftChild.sumOnPrefix, leftChild.sumOnSegment + rightChild.sumOnPrefix);
    crossedNode.sumOnSuffix = max(rightChild.sumOnSuffix, leftChild.sumOnSuffix + rightChild.sumOnSegment);
    crossedNode.answer = max(leftChild.sumOnSuffix + rightChild.sumOnPrefix, max(leftChild.answer, rightChild.answer));
    return crossedNode;
}

//  Function, that building a tree recursive
void build(int *base, Node *tree, int currentNode, int left, int right) {
    if (left == right) {
        tree[currentNode] = Node(base[left]);
    } else {
        int leftChild = 2 * currentNode;
        int middle = (left + right) / 2;
        build(base, tree, leftChild, left, middle);
        build(base, tree, leftChild + 1, middle + 1, right);
        // Use the previously described function to get the value of parent by his children
        tree[currentNode] = mergeNodes(tree[leftChild], tree[leftChild + 1]);
    }
}

//  Function, that return node, storing the answer to the problem (subsegment with a maximum amount)
Node answer(Node *tree, int currentNode, int left, int right, int leftBorder, int rightBorder) {
    if (left == leftBorder && right == rightBorder) {
        return tree[currentNode];
    }
    int leftChild = 2 * currentNode;
    int middle = (left + right) / 2;
    if (rightBorder <= middle) {
        return answer(tree, leftChild, left, middle, leftBorder, rightBorder);
    }
    if (leftBorder > middle) {
        return answer(tree, leftChild + 1, middle + 1, right, leftBorder, rightBorder);
    }
    return mergeNodes(answer(tree, leftChild, left, middle, leftBorder, middle),
        answer(tree, leftChild + 1, middle + 1, right, middle + 1, rightBorder));
}

int main() {
    std::ios::sync_with_stdio(false);
    unsigned int quantityOfNumbers;
    cin >> quantityOfNumbers;
    int *base = new int[quantityOfNumbers];     //  A given sequence of numbers 
    for (unsigned int indexOfNumber = 0; indexOfNumber < quantityOfNumbers; indexOfNumber++) {
        cin >> base[indexOfNumber];
    }
    int sizeOfTree = 2 * lowestBiggerPowOf2Than(quantityOfNumbers);
    Node *tree = new Node[sizeOfTree];
    build(base, tree, 1, 0, quantityOfNumbers - 1);
    unsigned int quantityOfRequests;
    cin >> quantityOfRequests;
    for (unsigned int indexOfRequest = 0; indexOfRequest < quantityOfRequests; indexOfRequest++) {
        unsigned int leftBorder, rightBorder;
        cin >> leftBorder >> rightBorder;
        cout << answer(tree, 1, 0, quantityOfNumbers - 1, leftBorder - 1, rightBorder - 1).answer << endl;
    }
    return 0;
}

#include <cmath>

#include <iostream>

#define INF -15008

using namespace std;

// Function, that teturn lowest power of 2, bigger than a given number

int lowestBiggerPowOf2Than(int number) {

int answer;

answer = 1 << (int)(log2((double)number - 1) + 1);

return answer;

}

// The structure describing the components from which consists a tree

struct Node {

int answer;

int sumOnPrefix;

int sumOnSuffix;

int sumOnSegment;

// Empty node takes the value less by 1 than what we can get, because we are looking for maximum subsegment

Node() {

answer = INF;

sumOnPrefix = INF;

sumOnSuffix = INF;

sumOnSegment = INF;

}

// Constructs a node by a value of the initial sequence of numbers

Node(int value) {

answer = value;

sumOnPrefix = value;

sumOnSuffix = value;

sumOnSegment = value;

}

};

// Function, that merges two nodes (childs) and returns new node (parent)

Node mergeNodes(Node leftChild, Node rightChild) {

Node crossedNode;

crossedNode.sumOnSegment = leftChild.sumOnSegment + rightChild.sumOnSegment;

crossedNode.sumOnPrefix = max(leftChild.sumOnPrefix, leftChild.sumOnSegment + rightChild.sumOnPrefix);

crossedNode.sumOnSuffix = max(rightChild.sumOnSuffix, leftChild.sumOnSuffix + rightChild.sumOnSegment);

crossedNode.answer = max(leftChild.sumOnSuffix + rightChild.sumOnPrefix, max(leftChild.answer, rightChild.answer));

return crossedNode;

}

// Function, that building a tree recursive

void build(int *base, Node *tree, int currentNode, int left, int right) {

if (left == right) {

tree[currentNode] = Node(base[left]);

} else {

int leftChild = 2 * currentNode;

int middle = (left + right) / 2;

build(base, tree, leftChild, left, middle);

build(base, tree, leftChild + 1, middle + 1, right);

// Use the previously described function to get the value of parent by his children

tree[currentNode] = mergeNodes(tree[leftChild], tree[leftChild + 1]);

}

// Function, that return node, storing the answer to the problem (subsegment with a maximum amount)

Node answer(Node *tree, int currentNode, int left, int right, int leftBorder, int rightBorder) {

if (left == leftBorder && right == rightBorder) {

return tree[currentNode];

}

int leftChild = 2 * currentNode;

int middle = (left + right) / 2;

if (rightBorder <= middle) {

return answer(tree, leftChild, left, middle, leftBorder, rightBorder);

}

if (leftBorder > middle) {

return answer(tree, leftChild + 1, middle + 1, right, leftBorder, rightBorder);

}

return mergeNodes(answer(tree, leftChild, left, middle, leftBorder, middle),

answer(tree, leftChild + 1, middle + 1, right, middle + 1, rightBorder));

}

int main() {

std::ios::sync_with_stdio(false);

unsigned int quantityOfNumbers;

cin >> quantityOfNumbers;

int *base = new int[quantityOfNumbers]; // A given sequence of numbers

for (unsigned int indexOfNumber = 0; indexOfNumber < quantityOfNumbers; indexOfNumber++) {

cin >> base[indexOfNumber];

}

int sizeOfTree = 2 * lowestBiggerPowOf2Than(quantityOfNumbers);

Node *tree = new Node[sizeOfTree];

build(base, tree, 1, 0, quantityOfNumbers - 1);

unsigned int quantityOfRequests;

cin >> quantityOfRequests;

for (unsigned int indexOfRequest = 0; indexOfRequest < quantityOfRequests; indexOfRequest++) {

unsigned int leftBorder, rightBorder;

cin >> leftBorder >> rightBorder;

cout << answer(tree, 1, 0, quantityOfNumbers - 1, leftBorder - 1, rightBorder - 1).answer << endl;

}

return 0;

}

C++ для приматов

Начальный курс программирования для студентов направления "Прикладная математика" Одесского национального университета имени И.И.Мечникова

e-olymp 2906. Can you answer these queries — 1

Input

Output

Tests

Algorithm

Code

Links

Related Images:

Понравилось это:

Похожее

Добавить комментарий Отменить ответ

Input

Output

Tests

Algorithm

Code

Links

Related Images:

Поделиться ссылкой:

Понравилось это:

Похожее

Добавить комментарий Отменить ответ