715

class RangeModule {
public:
    map<int, int> m;
    RangeModule() {

    }

    void addRange(int left, int right) {
        auto it = m.upper_bound(left);
        if(it != m.begin() && prev(it)->second >= left){
            left = prev(it)->first;
        }
        m[left] = removeIntervals(left, right);
    }

    bool queryRange(int left, int right) {
        auto it = m.upper_bound(left);
        if(it != m.begin())
            it--;
        return (left >= it->first && right <= it->second);
    }

    void removeRange(int left, int right) {
        int nextRight = removeIntervals(left, right);
        auto it = m.lower_bound(left);
        if(it != m.begin()){
            it--;
            nextRight = max(nextRight, it->second);
            it->second = min(it->second, left);
        }
        if(nextRight > right)
            m[right] = nextRight;
    }

    int removeIntervals(int left, int right){
        int r = right;
        for(auto it = m.lower_bound(left); it != m.end() && it->first <= right; ){
            r = max(r, it->second);
            m.erase(it++);
        }
        return r;
    }

};

/**
 * Your RangeModule object will be instantiated and called as such:
 * RangeModule* obj = new RangeModule();
 * obj->addRange(left,right);
 * bool param_2 = obj->queryRange(left,right);
 * obj->removeRange(left,right);
 */