using pll=pair<int,int>;
class SummaryRanges {
public:
set<pll>itv;
set<int>added;
void p(pll P)
{
auto nx=itv.lower_bound(P);
--nx;auto pv=nx;nx++;
auto[lp,rp]=*pv;auto[ln,rn]=*nx;auto&[l,r]=P;
if(ln==r)r=rn,itv.erase(nx);
if(rp==l)l=lp,itv.erase(pv);
itv.insert(P);
}
SummaryRanges() {
itv.emplace(-9,-9);
itv.emplace(1e9+7,1e9+7);
}
void addNum(int value) {
if(!added.count(value))
{
added.insert(value);
p({value,value+1});
}
}
vector<vector<int>> getIntervals() {
vector<vector<int>>vv;
for(auto&[i,j]:itv)if(i!=j)vv.push_back({i,j-1});
return vv;
}
};
예전에 구간 관리를 추가/삭제 O(logn)에 시키는 백준 문제를 푼 적 있어서 달달하게 챙겨감
해당 댓글은 삭제되었습니다.
그냥 트리셋을 어떻게든 잘 관리하는 풀이입니다. CLRS에 나오는 "구간 트리"와 어쩌면 비슷할지도 모르겠네요