729. 我的日程安排表 I(set or 动态开点线段树)

729. 我的日程安排表 I(set or 动态开点线段树)

区间覆盖，区间查询。因此值域大，查询次数小，所以动态开点。

建树方法与普通线段树类似，就是pushdown的时候特判下左右儿子是否位空，然后所有函数都用指针即可。

时间复杂度：$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，做法每次就lower_bound l>=ed的 位置$p$。

然后判断$(--p)\to r\le st<ed\le l$

时间复杂度：$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;
    }
};