#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();
}