상자 보관 (JUNGOL 8607)

https://jungol.co.kr/problem/8607

---

아이디어

s와 c가 주어지면 구간 (c,s]에 표시를 해줍시다. 그리고 어떠한 점 x에 대하여 x에 표시된 개수를 세어줄것입니다. 모든 x에 대하여 표시된 값의 개수의 최댓값이 정답이 됩니다.

 

증명) 표시된 값의 개수의 최댓값을 P_mx라고 합시다. 정답값이 P_mx이상임은 자명합니다. 어떠한 x에 대하여 표시된 값의 개수가 P_mx라는것인데, 그 표시된 P_mx개의 구간은 서로를 포함할 수 없기 때문입니다. 그러면 정답값이 P_mx이하임은 어떻게 증명할까요?

모든 구간을 c가 증가하는 순서대로, c가 같다면 s가 증가하는 순서대로 정렬해줍시다. 그리고 앞에서부터 구간을 하나씩 넣어줄것입니다. 첫번째 구간은 대표구간1이 됩니다. 만약 i번째 구간을 넣을 때 어떠한 j가 존재하여 대표구간 j를 구간 i가 포함한다면, 대표구간 j를 구간 i로 바꿉니다. 만약 그러한 j가 존재하지 않는다면 구간 i를 새로운 대표구간으로 만듭니다. 이때 대표구간의 개수는 P_mx이하입니다. 만약 대표구간의 개수가 P_mx초과인 순간이 있다면, 어떠한 구간 i에 대하여 P_mx+1개의 구간이 존재하여 구간 i와 겹친다는 것인데, 그것은 P_mx의 정의에 모순되기 때문입니다.

 

그러므로 (c,s]에 표시를 하고 최댓값을 구하는 것을 값 압축과 세그먼트 트리를 이용하여 빠르게 구해주면 됩니다.

---

소스코드

#include <iostream>
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;

ll tree[1616161]={0},lazy[1616161]={0};
void pp(ll s,ll e,ll node)
{
    tree[node]+=lazy[node];
    if (s!=e)
    {
        lazy[node*2]+=lazy[node];
        lazy[node*2+1]+=lazy[node];
    }
    lazy[node]=0;
}
void update(ll s,ll e,ll node,ll l,ll r)
{
    pp(s,e,node);
    if (e<l || r<s) return;
    if (l<=s && e<=r)
    {
        lazy[node]=1;
        pp(s,e,node);
        return;
    }
    ll mid=(s+e)/2;
    update(s,mid,node*2,l,r);
    update(mid+1,e,node*2+1,l,r);
    tree[node]=max(tree[node*2],tree[node*2+1]);
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll N,i,a,b;
    vector <pair <ll,ll> > Query;
    vector <ll> nums;

    cin>>N;
    for (i=0;i<N;i++)
    {
        cin>>b>>a;
        Query.push_back({a,b});
        nums.push_back(a);
        nums.push_back(b);
    }

    sort (nums.begin(),nums.end());

    for (i=0;i<N;i++)
    {
        a=lower_bound(nums.begin(),nums.end(),Query[i].first)-nums.begin()+1;
        b=lower_bound(nums.begin(),nums.end(),Query[i].second)-nums.begin()+1;

        update(1,2*N,1,a+1,b);
        cout<<tree[1]+lazy[1]<<"\n";
    }
}