LineTree.cpp

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