Sunday, October 26, 2014

SPOJ Problem Set (classical) - Horrible Queries

Problem:

Solution:

Using the segment tree like in SPOJ_LITE_2. This time the summary is the sum instead of on light count, but it is just as easy to update those summaries.

Code:

#include "stdafx.h"

// http://www.spoj.com/problems/HORRIBLE/

#include "SPOJ_HORRIBLE.h"

#include <iostream>

typedef long long int64;

namespace _SPOJ_HORRIBLE
{
class SegmentTree
{
public:
SegmentTree(int size);
void add_constant(int from, int to, int64 value);
int64 query(int from, int to);
void print() const;
private:
class SegmentTreeNode
{
public:
SegmentTreeNode(int from, int to);

void add_constant(int from, int to, int64 value);
int64 query(int from, int to);

void print(int indent) const;

int from;
int to;
SegmentTreeNode* left;
SegmentTreeNode* right;
int64 sum;
private:
};

SegmentTreeNode* build_tree(int from, int to) const;

SegmentTreeNode* root;
};
};

using namespace _SPOJ_HORRIBLE;
using namespace std;

SegmentTree::SegmentTree(int size)
{
this->root = this->build_tree(0, size);
}

SegmentTree::SegmentTreeNode* SegmentTree::build_tree(int from, int to) const
{
SegmentTree::SegmentTreeNode* result = new SegmentTree::SegmentTreeNode(from, to);
int size = to - from;
if (size == 1)
{
// no-op, children are NULL already
}
else if (size > 1)
{
int left_size = size / 2;
int split = from + left_size;
result->left = this->build_tree(from, split);
result->right = this->build_tree(split, to);
}
else
{
throw 0;
}

return result;
}

void SegmentTree::add_constant(int from, int to, int64 value)
{
}

int64 SegmentTree::query(int from, int to)
{
return this->root->query(from, to);
}

void SegmentTree::print() const
{
this->root->print(0);
}

SegmentTree::SegmentTreeNode::SegmentTreeNode(int from, int to) : from(from), to(to), left(NULL), right(NULL), sum(0), pending_to_add_to_children(0)
{
}

void SegmentTree::SegmentTreeNode::add_constant(int from, int to, int64 value)
{
if (this->from == from && this->to == to)
{
this->sum += value * (to - from);
}
else
{
{
}

this->sum = 0;

if (this->left != NULL)
{
int left_from = from;
int left_to = min(this->left->to, to);
if (left_to - left_from > 0)
{
}

this->sum += this->left->sum;
}

if (this->right != NULL)
{
int right_from = max(this->right->from, from);
int right_to = to;
if (right_to - right_from > 0)
{
}

this->sum += this->right->sum;
}
}
}

int64 SegmentTree::SegmentTreeNode::query(int from, int to)
{
if (this->from == from && this->to == to)
{
return this->sum;
}
else
{
{
}

int64 result = 0;

if (this->left != NULL)
{
int left_from = from;
int left_to = min(this->left->to, to);
if (left_to - left_from > 0)
{
result += this->left->query(left_from, left_to);
}
}

if (this->right != NULL)
{
int right_from = max(this->right->from, from);
int right_to = to;
if (right_to - right_from > 0)
{
result += this->right->query(right_from, right_to);
}
}

return result;
}
}

{
{
throw 0;
}
if (this->left != NULL)
{
if (this->right == NULL)
{
throw 0;
}

}
}

void SegmentTree::SegmentTreeNode::print(int indent) const
{
if (this == NULL)
{
return;
}

for (int i = 0; i < indent; i++)
{
cout << ' ';
}
cout << "[" << this->from << ", " << this->to << ") has sum = " << this->sum << " . Children need to add (" << this->pending_to_add_to_children << ")" << endl;
this->left->print(indent + 2);
this->right->print(indent + 2);
}

int SPOJ_HORRIBLE()
{
int num_test_cases;
cin >> num_test_cases;
for (int c = 0; c < num_test_cases; c++)
{
int num_elements;
int num_operations;
cin >> num_elements;
cin >> num_operations;
SegmentTree tree(num_elements);
for (int q = 0; q < num_operations; q++)
{
int operation_id;
int from;
int to;
cin >> operation_id;
cin >> from;
cin >> to;

// Converting the input one base inclusive/inclusive index to zero base inclusive/exclusive index
from--;

if (operation_id == 0)
{
int value;
cin >> value;
}
else
{
int64 query_result = tree.query(from, to);
cout << query_result << endl;
}
}
}

return 0;
}