Truth Tellers (JUNGOL 4973)

https://jungol.co.kr/problem/4973?cursor=MTIsMSw0

---

아이디어

어떠한 x에 대하여 x가 A_i이상 B_i이하인 i의 개수가 x이상이여야합니다. 그러기 위해서는 초기에 arr[1]=-1, arr[2]=-2, ... arr[N]=-N으로 저장한 다음, A_i, B_i가 주어지면 [A_i,B_i]에 1을 더해주는 쿼리를 느리게 갱신되는 세그먼트 트리로 처리해준 다음, arr배열에서 0이상의 수가 존재하는 가장 큰 인덱스를 찾아주면 됩니다.

---

소스코드

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

ll tree[2020202]={0},lazy[2020202]={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,ll num)
{
    pp(s,e,node);
    if (e<l || r<s) return;
    if (l<=s && e<=r)
    {
        lazy[node]=num;
        pp(s,e,node);
        return;
    }

    ll mid=(s+e)/2;
    update(s,mid,node*2,l,r,num);
    update(mid+1,e,node*2+1,l,r,num);
    tree[node]=max(tree[node*2],tree[node*2+1]);
}
ll MaxIdx(ll s,ll e,ll node)
{
    pp(s,e,node);
    if (s==e) return s;
    ll mid=(s+e)/2;

    pp(s,mid,node*2),pp(mid+1,e,node*2+1);
    if (tree[node*2+1]>=0) //오른쪽 범위에 0이상인 수가 있다
        return MaxIdx(mid+1,e,node*2+1);
    return MaxIdx(s,mid,node*2);
}

ll L[505050]={0},R[505050]={0};

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll N,i;

    cin>>N;
    for (i=1;i<=N;i++) update(0,N,1,i,i,-i);
    for (i=1;i<=N;i++)
    {
        cin>>L[i]>>R[i];
        update(0,N,1,L[i],R[i],1);
    }

    cout<<MaxIdx(0,N,1)<<' ';

    ll Q,a,b,c;
    cin>>Q;
    for (i=1;i<=Q;i++)
    {
        cin>>a>>b>>c;
        update(0,N,1,L[a],R[a],-1);
        L[a]=b,R[a]=c;
        update(0,N,1,L[a],R[a],1);

        cout<<MaxIdx(0,N,1)<<' ';
    }
}