ACM - 선분 트 리

#include <iostream>

using namespace std;
#define MAXN 100
struct Node
{
    int left,right,mid;
    int cover;//         
}seg_tree[4*MAXN];//      4   
void build(int l,int r,int num)//l,r          ,num          
{
    cout<<num<<" "<<l<<" "<<r<<endl;
    seg_tree[num].left=l;
    seg_tree[num].right=r;
    seg_tree[num].mid=(l+r)/2;
    seg_tree[num].cover=0;
    if(l+1!=r)//       
    {
        build(l,seg_tree[num].mid,2*num);
        build(seg_tree[num].mid,r,2*num+1);
    }
}
void insert(int l,int r,int num)
{
    if(seg_tree[num].left==l&&seg_tree[num].right==r)
    {
        //                     
        seg_tree[num].cover=1;
        //cout<<num<<endl;
        return;
    }
    if(r<=seg_tree[num].mid)
    {
        //                      
        insert(l,r,2*num);
    }
    else if(l>=seg_tree[num].mid)//                      
            insert(l,r,2*num+1);
    else
    {
        //                    
        insert(l,seg_tree[num].mid,2*num);
        insert(seg_tree[num].mid,r,2*num+1);
    }
}
bool del(int l,int r,int num)
{
    if(seg_tree[num].left+1==seg_tree[num].right)
    {
        //         
        int f = seg_tree[num].cover;
        seg_tree[num].cover=0;
        return f;
    }
    if(seg_tree[num].cover==1)//             
    {
        seg_tree[num].cover=0;//     
        seg_tree[2*num].cover=1;//    1
        seg_tree[2*num+1].cover=1;//    1
    }
    if(r<=seg_tree[num].mid)//                      
        return del(l,r,2*num);
    else if(l>=seg_tree[num].mid)//                      
    {
        return del(l,r,2*num+1);
    }
    else
        return del(l,seg_tree[num].mid,2*num)&&
               del(seg_tree[num].mid,r,2*num+1);
} 

좋은 웹페이지 즐겨찾기