729. My schedule I (set or dynamic open point segment tree)

729. My schedule I(set or Dynamic open point line segment tree )

Interval coverage , Interval query . Therefore, the value range is large , Small number of queries , So open it dynamically .

The tree building method is similar to the ordinary segment tree , Namely pushdown It is decided whether the left and right sons are empty , Then all functions can use pointers .

Time complexity ：$O(nlogC)$

class MyCalendar {
    
public:
    struct node{
    
    	node *l,*r;
    	int s,lz;
    };
	node * rt = new node();
	const int  NN = 1e9;
    MyCalendar() {
    
	
    }
    void re(node* a){
    
    	a->s=a->l->s|a->r->s;
    }
    void pd(node* a){
    
    	if(a->l==NULL) a->l= new node();
    	if(a->r==NULL) a->r= new node();
    	if(!a->lz) return;
    	a->l->s=a->lz;
    	a->r->s=a->lz;
    	a->l->lz=a->r->lz=a->lz;
    	a->lz=0;
    }
    
    void upd(node *a,int l,int r,int L,int R,int v){
    
    	if(l>=L&&r<=R){
    
    		a->s=v;
    		a->lz=v;return;
    	}
    	pd(a);
    	int m = l+r>>1;
    	if(L<=m) upd(a->l,l,m,L,R,v);
    	if(R>m) upd(a->r,m+1,r,L,R,v);
    	re(a);
    }
    bool que(node *a,int l,int r,int L,int R){
    
    	if(l>=L&&r<=R) return a->s;
    	int m = l+r>>1;
    	pd(a);
    	int ok=0;
    	if(L<=m) ok|=que(a->l,l,m,L,R);
    	if(R>m) ok|=que(a->r,m+1,r,L,R);
    	return ok;
    }
    bool book(int st, int ed) {
    
		if(que(rt,0,NN,st,ed-1)) return false;
		upd(rt,0,NN,st,ed-1,1);
		return true;
    }
    
};

set, Practice every time lower_bound l>=ed Of Location $p$.

And then determine $(--p)\to r\le st<ed\le l$

Time complexity ：$O(nlogn)$

class MyCalendar {
    
    set<pair<int, int>> booked;

public:
    bool book(int start, int end) {
    
        auto it = booked.lower_bound({
    end, 0});
        if (it == booked.begin() || (--it)->second <= start) {
    
            booked.emplace(start, end);
            return true;
        }
        return false;
    }
};