pascal:
Program IntervalTree;
Const Maxn=10000;
Inf='Input.txt';
Ouf='Output.txt';
Type TreeNode=Record
a,b,Left,Right,Cover:Longint;
End;
Var Tree:array [1..Maxn] of TreeNode;
Number,Tot,c,d:Longint;
Procedure MakeTree(a,b:Longint);
Var Now:Longint;
Begin
Inc(Tot);
Now:=Tot;
Tree[Now].a:=a; Tree[Now].b:=b; Tree[Now].Cover:=0;
If a+1<b then begin
Tree[Now].Left:=Tot+1;
MakeTree(a,(a+b) div 2);
Tree[Now].Right:=Tot+1;
MakeTree((a+b) div 2,b);
End;
End;
Procedure Insert(Num:Longint);
Begin
If (c<=Tree[Num].a) and (Tree[Num].b<=d) then
Tree[Num].Cover:=Tree[Num].Cover+1
Else begin
If c<(Tree[Num].a+Tree[Num].b) div 2 then Insert(Tree[Num].Left);
If d>(Tree[Num].a+Tree[Num].b) div 2 then Insert(Tree[Num].Right);
End;
End;
Procedure Delete(Num:Longint);
Begin
If (c<=Tree[Num].a) and (Tree[Num].b<=d) then
Dec(Tree[Num].Cover)
Else begin
If c<(Tree[Num].a+Tree[Num].b) div 2 then Delete(Tree[Num].Left);
If d>(Tree[Num].a+Tree[Num].b) div 2 then Delete(Tree[Num].Right);
End;
End;
Procedure Count(Num:longint);
Begin
If Tree[Num].Cover>0 then
Number:=Number+(Tree[Num].b-Tree[Num].a)
Else begin
If Tree[Num].Left>0 then Count(Tree[Num].Left);
If Tree[Num].Right>0 then Count(Tree[Num].Right);
End;
End;
Begin
Assign(Input,Inf);Reset(Input);
Assign(Output,ouf);Rewrite(Output);
Readln(c,d);
MakeTree(c,d);
While not eof do Begin
Readln(c,d);
Insert(1);
End;
Count(1);
Writeln(Number);
Close(Output);
Close(Input);
End.
C++:
#include<iostream>
using namespace std;
#define Maxn 10000
struct Node{
int a,b,left,right,cover;
};
Node Tree[Maxn];
int Number,Tot,c,d;
void build(int a,int b){
int Now;
Tot++;
Now=Tot;
Tree[Now].a=a;
Tree[Now].b=b;
Tree[Now].cover=0;
if(b-a>1){
int mid=(a+b)>>1;
Tree[Now].left=Tot+1;
build(a,mid);
Tree[Now].right=Tot+1;
build(mid,b);
}
}
void insert(int Num){
if(c<=Tree[Num].a&&Tree[Num].b<=d)
Tree[Num].cover++;
else{
int mid=(Tree[Num].a+Tree[Num].b)>>1;
if(c<=mid)
insert(Tree[Num].left);
if(d>=mid)
insert(Tree[Num].right);
}
}
void del(int Num){
if(c<=Tree[Num].a&&Tree[Num].b<=d)
Tree[Num].cover--;
else{
int mid=(Tree[Num].a+Tree[Num].b)>>1;
if(c<=mid)
insert(Tree[Num].left);
if(d>=mid)
insert(Tree[Num].right);
}
}
void Count(int Num){
if(Tree[Num].cover)
Number+=(Tree[Num].b-Tree[Num].a);
else{
if(Tree[Num].left)
Count(Tree[Num].left);
if(Tree[Num].right)
Count(Tree[Num].left);
}
}
int main()
{
scanf("%d%d",&c,&d);
build(c,d);
while(scanf("%d%d",&c,&d)!=EOF)
insert(1);
Number=0;
Count(1);
printf("%d\n",Number);
return 0;
}
//线段树的实现
#include <stdio.h>
#include <alloc.h>
#define MaxSize 1000
typedef char ElemType;
typedef struct node
{
int i,j;
int cover;
struct node *lchild,*rchild;
} ITree;
//建立线段树
ITree *CreateTree(int a,int b)
{
ITree *r;
if(b<a) return NULL;
r=(ITree *)malloc(sizeof(ITree));
r->i=a;r->j=b;r->cover=0;
if(b-a>1)
{
r->lchild=CreateTree(a,(a+b)/2);
r->rchild=CreateTree((a+b)/2,b);
}
else r->lchild=r->rchild=NULL;
return r;
}
//线段树的插入
void InsTree(ITree *r,int a,int b)
{
int mid;
if(a<=r->i&&r->j<=b) r->cover++;
else
{
mid=(r->i+r->j)/2;
if(b<=mid) InsTree(r->lchild,a,b);
else if(mid<=a) InsTree(r->rchild,a,b);
else
{
InsTree(r->lchild,a,mid);
InsTree(r->rchild,mid,b);
}
}
}
//线段树的删除
void DelTree(ITree *r,int a,int b)
{
int mid;
if(a<=r->i&&r->j<=b) r->cover--;
else
{
mid=(r->i+r->j)/2;
if(b<=mid) DelTree(r->lchild,a,b);
else if(mid<=a) DelTree(r->rchild,a,b);
else
{
DelTree(r->lchild,a,mid);
DelTree(r->rchild,mid,b);
}
}
}
//计算线段树的测度
int Count(ITree *r)
{
if(r->cover>0) return r->j-r->i;
else if(r->j-r->i==1) return 0;
else return Count(r->lchild)+Count(r->rchild);
}
//主函数
int main()
{
ITree *r;
int a,b,a1,b1,a2,b2,a3,b3,n,i;
printf("请输入线段树的区间端点：");
while(scanf("%d%d",&a,&b)!=EOF)
{
r=CreateTree(a,b);
printf("请输入插入3条线段的区间端点：");
scanf("%d%d%d%d%d%d",&a1,&b1,&a2,&b2,&a3,&b3);
InsTree(r,a1,b1);InsTree(r,a2,b2);InsTree(r,a3,b3);
printf("插入3条线段后线段树的测度为%d\n",Count(r));
printf("请输入删除2条线段的区间端点：");
scanf("%d%d%d%d",&a1,&b1,&a2,&b2);
DelTree(r,a1,b1);DelTree(r,a2,b2);
printf("删除2条线段后线段树的测度为%d\n",Count(r));
printf("\n请输入线段树的区间端点：");
}
return 0;
}
posted on 2009-04-22 14:21
xfstart07 阅读(646)
评论(0) 编辑 收藏 引用 所属分类:
代码库