#include <cstdlib>
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

struct Segment
{
Segment(int left, int right)
: left_(left), right_(right)
{}

int left(void) const { return left_; }
int right(void) const { return right_; }

void set(int left, int right) { left_ = left; right_ = right; }

private:
int left_;
int right_;
};

struct SegmentTreeNode
{
explicit SegmentTreeNode(Segment segment, SegmentTreeNode *leftPtr = NULL, SegmentTreeNode *rightPtr = NULL)
:segment_(segment), maxRight_(segment.right()) , left_(leftPtr), right_(rightPtr)
{}

Segment segment() const { return segment_; }
int maxRight() const { return maxRight_; }

struct SegmentTreeNode *&left() { return left_; }
struct SegmentTreeNode *&right() { return right_; }
void setMaxRight(int r) { maxRight_ = r; }

void setLeft(struct SegmentTreeNode *left) { left_ = left; }
void setRight(struct SegmentTreeNode *right) { right_ = right; }

int key() { return segment_.left(); }

void setSegment(Segment s) { segment_ = s; }

private:
Segment segment_;
int maxRight_;
struct SegmentTreeNode *left_;
struct SegmentTreeNode *right_;
};

struct SegmentTree
{
SegmentTree(SegmentTreeNode *root)
{
root_ = root;
}

SegmentTreeNode *&getRoot() { return root_; }

void add(Segment seg);
bool del(Segment seg);
SegmentTreeNode *find(Segment seg);

void intersect(Segment seg, std::vector<Segment> &intersects);

private:
SegmentTreeNode *root_;
};

int main(void)
{
char *fileName = "test.txt";

std::ifstream in(fileName);

SegmentTree tree(NULL);

size_t treeSize = 0;
in » treeSize;

for (size_t i = 0; i < treeSize; ++i)
{
int u = 0;
int v = 0;

in » u » v;

tree.add(Segment(u, v));
}

std::vector<Segment> intersects;

tree.intersect(Segment(-42, -40), intersects);

std::cout « intersects.size() « std::endl;

if (tree.del(Segment(-40, 20)))
{
std::cout « "Delete of the segment was complete\n";
std::cout « tree.getRoot()->maxRight() « std::endl;
}

return 0;
}

void SegmentTree::add(Segment seg)
{
const int minVal = -1000000;

SegmentTreeNode *newNode = new SegmentTreeNode(seg);
SegmentTreeNode *curNode = root_;
SegmentTreeNode *parentNode = curNode;
bool toLeft = true;

if (root_ == NULL)
{
root_ = newNode;
return;
}

while (curNode != NULL)
{
int v1 = minVal;
int v2 = minVal;

curNode->setMaxRight(std::max(newNode->maxRight(), curNode->maxRight()));

if (newNode->key() <= curNode->key())
{
parentNode = curNode;
curNode = curNode->left();

toLeft = true;
} else
{
parentNode = curNode;
curNode = curNode->right();

toLeft = false;
}
}

if (toLeft)
{
parentNode->setLeft(newNode);
} else
{
parentNode->setRight(newNode);
}
}

bool SegmentTree::del(Segment seg)
{
const int minVal = -1000000;

std::stack<SegmentTreeNode *> st;

SegmentTreeNode *node = root_;

while (node != NULL && ( node->segment().left() != seg.left() || node->segment().right() != seg.right() ))
{
st.push(node);

if (seg.left() <= node->key())
{
node = node->left();
} else
{
node = node->right();
}
}

if (node == NULL)
{
return false;
} else
{
SegmentTreeNode *replaceNode = node;

std::cout « replaceNode->segment().right() « std::endl;

while (node->right() != NULL)
{
st.push(node);
node = node->right();
}

std::cout « replaceNode->segment().right() « std::endl;

//Node points to vertex, which we must delete
replaceNode->segment().set(node->segment().left(), node->segment().right());
replaceNode->setMaxRight(node->segment().right());

int counter = 0;
SegmentTreeNode * deleteNode = node;

while (!st.empty())
{
node = st.top();
st.pop();

if (counter == 0)
{
++counter;
if (node->left() == deleteNode)
node->setLeft(NULL);
else
node->setRight(NULL);

delete deleteNode;
}

int v1 = minVal;
int v2 = minVal;

if (node->left() != NULL)
v1 = node->left()->maxRight();
if (node->right() != NULL)
v2 = node->right()->maxRight();
04:41:09
node->setMaxRight( std::max(node->segment().right(), (v1 > v2) ? v1 : v2) );
}

return true;
}
}

SegmentTreeNode *SegmentTree::find(Segment seg)
{
SegmentTreeNode *node = root_;

while (node != NULL && ( node->segment().left() != seg.left() || node->segment().right() != seg.right() ))
{
if (seg.left() <= node->key())
node = node->left();
else
node = node->right();
}

return node;
}

void SegmentTree::intersect(Segment seg, std::vector<Segment> &intersects)
{
std::stack<SegmentTreeNode *> st;
SegmentTreeNode *node = root_;

st.push(node);

while (!st.empty())
{
node = st.top();
st.pop();

while (node != NULL && (seg.right() < node->segment().left() || seg.left() > node->segment().right()))
{
if (node->right() != NULL && node->right()->maxRight() >= seg.left())
st.push(node->right());

if (node->left() != NULL && node->left()->maxRight() >= seg.left())
{
node = node->left();
} else
{
node = node->right();
}
}

if (node != NULL)
{
st.push(node->left());
st.push(node->right());

intersects.push_back(node->segment());
}
}
}