const int MAXN = 50000;
class SegmentTree {
public:
int LSON[MAXN]; //LSON[i]为节点i的左儿子的序号
int RSON[MAXN]; //RSON[i]为节点i的右儿子的序号
int B[MAXN]; //B[i]为区间i左端点
int E[MAXN]; //E[i]为区间i右端点
int cnt[MAXN]; //cnt[i]为区间i的计数器
int M[MAXN]; //M[i]为区间i的测度
int lbd[MAXN]; //lbd[i]为区间i的左端点是否被覆盖
int rbd[MAXN]; //rbd[i]为区间i的右端点是否被覆盖
int lines[MAXN]; //lines[i]为区间i的连续线段数
int root; //树根 初始化时候设为1
int n; //树的节点数
SegmentTree(int, int);
void build(int, int);
void insert(int, int, int);
void del(int, int, int);
void updateM(int); //更新测度
void updateLines(int); //更新连续线段数
};
SegmentTree::SegmentTree(int a, int b) {
root = 1;
n = 0;
memset(LSON, 0, sizeof(LSON));
memset(RSON, 0, sizeof(RSON));
memset(cnt, 0, sizeof(cnt));
memset(M, 0, sizeof(M));
memset(lines, 0, sizeof(lines));
memset(lbd, 0, sizeof(lbd));
memset(rbd, 0, sizeof(rbd));
build(a, b);
}
void SegmentTree::build(int a, int b) {
n += 1;
int v = n;
B[v] = a; E[v] = b;
if (b - a > 1) {
LSON[v] = n + 1;
build(a, (a+b)/2);
RSON[v] = n + 1;
build((a+b)/2, b);
}
}
void SegmentTree::insert(int a, int b, int v) {
if (!v) return ;
if (a <= B[v] && E[v] <= b) {
cnt[v]++;
lbd[v] = rbd[v] = 1;
} else if (E[v]-B[v] > 1) {
if (a <(b[v]+e[v])/2) insert(a, b, LSON[v]);
if (b > (B[v]+E[v])/2) insert(a, b, RSON[v]);
}
updateM(v);
updateLines(v);
}
void SegmentTree::del(int a, int b, int v) {
if (!v) return ;
if (a <= B[v] && E[v] <= b) {
cnt[v]--;
if (a == B[v]) lbd[v] = 0;
if (b == E[v]) rbd[v] = 0;
} else if (E[v]-B[v] > 1) {
if (a <(b[v]+e[v])/2) del(a, b, LSON[v]);
if (b > (B[v]+E[v])/2) del(a, b, RSON[v]);
}
updateM(v);
updateLines(v);
}
void SegmentTree::updateM(int v) {
if (cnt[v] > 0) M[v] = E[v] - B[v];
else {
if (E[v]-B[v] == 1) M[v] = 0;
else M[v] = M[LSON[v]] + M[RSON[v]];
}
}
void SegmentTree::updateLines(int v) {
if (cnt[v] > 0) lbd[v] = rbd[v] = lines[v] = 1;
else {
if (E[v]-B[v] == 1) lbd[v] = rbd[v] = lines[v] = 0;
else {
lbd[v] = lbd[LSON[v]]; rbd[v] = rbd[RSON[v]];
lines[v] = lines[LSON[v]] + lines[RSON[v]] - rbd[LSON[v]] * lbd[RSON[v]];
}
}
}
posted on 2007-04-07 12:16
豪 阅读(925)
评论(1) 编辑 收藏 引用 所属分类:
数据结构与算法