#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
const int SIZE = 10010;
struct node // the node of line tree
{
int i,j; // 区间范围
node * lson;
node * rson;
int count; // 线段覆盖条数
int m; // 测度
int line; // 连续段数
int lbd,rbd; // 用来计算连续段数
node(int l,int r)
{
i = l,j = r;
count = m = line = lbd = rbd = 0;
lson = rson = NULL;
}
};
class LineTree
{
node * head;
/* 以下函数内部使用,可不用考虑 */
void init(node * pnode = NULL)
{
head = pnode;
}
void updateM()
{
if (head->count > 0) // 被覆盖满
head->m = head->j - head->i;
else if (head->j - head->i == 1) // 该节点为叶节点
head->m = 0;
else // 其他内部节点的情况
head->m = (head->lson)->m + (head->rson)->m;
}
void updateLine()
{
if (head->count > 0)
head->lbd = head->rbd = head->line = 1;
else if (head->j - head->i == 1)
head->lbd = head->rbd = head->line = 0;
else
{
head->lbd = (head->lson)->lbd;
head->rbd = (head->rson)->rbd;
head->line = (head->lson)->line + (head->rson)->line - (head->lson)->rbd * (head->rson)->lbd;
}
}
public:
LineTree();
void clear(); // 清空线段数;
void build(int l,int r); // 建立线段树,区间[l,r];
void insert(int l,int r); // 插入一条线段;
void del(int l,int r); // 删除一条线段;
int GetM(); // 测度;
int GetLine(); // 连续段数;
int GetCov(); // 覆盖线段数;
~LineTree();
};
LineTree::LineTree()
{
head = NULL;
}
void LineTree::clear() // 清空线段数
{
if (head == NULL)
return;
LineTree temp;
temp.init(head->lson);
temp.clear();
temp.init(head->rson);
temp.clear();
delete head;
head = NULL;
}
void LineTree::build(int l,int r) // 建立线段树,区间[l,r]
{
head = new node(l,r);
if (r - l > 1)
{
int k = (l + r) / 2;
LineTree temp;
temp.build(l,k);
head->lson = temp.head;
temp.init();
temp.build(k,r);
head->rson = temp.head;
}
}
void LineTree::insert(int l,int r) // 插入一条线段
{
if (l <= head->i && r >= head->j)
(head->count)++;
else
{
LineTree temp;
if (l < (head->i+head->j)/2)
{
temp.init(head->lson);
temp.insert(l,r);
}
if (r > (head->i+head->j)/2)
{
temp.init(head->rson);
temp.insert(l,r);
}
}
updateM();
updateLine();
}
void LineTree::del(int l,int r) // 删除一条线段
{
if (l <= head->i && head->j <= r)
(head->count)--;
else
{
LineTree temp;
if (l < (head->i+head->j)/2)
{
temp.init(head->lson);
temp.del(l,r);
}
if (r > (head->i+head->j)/2)
{
temp.init(head->rson);
temp.del(l,r);
}
}
updateM();
updateLine();
}
int LineTree::GetM() // 测度
{
return head->m;
}
int LineTree::GetLine() // 连续段数
{
return head->line;
}
int LineTree::GetCov() // 覆盖线段数
{
return head->count;
}
LineTree::~LineTree()
{
this->clear();
}