BOJ 16910(mex와 쿼리)풀이

solved.ac 티어 : 다이아 4

 

www.acmicpc.net/problem/16910

16910번: mex와 쿼리

생각보다 간단한 세그레이지이다.

1 l r: 구간 [l, r]에 속하는 모든 자연수를 배열 A에 추가한다. 배열에 이미 있는 자연수는 또 추가하지 않는다.

 

2 l r: 구간 [l, r]에 속하는 모든 자연수를 배열 A에서 제거한다.

 

3 l r: 구간 [l, r]에 속하는 모든 자연수 x에 대해서, 다음을 수행한다.

x가 배열 A에 있으면, 배열에서 제거

   x가 배열 A에 없으면, 배열에 추가한다

 

이때 추가를 1 제거를 0으로 해주면 된다.

1 번은 구간을 1로 바꿔 주고 2번은 구간을 0으로 3번은 xor을 해주면 된다.

이때 1번과 2번은 기존 값에서 덮어 씌어주면 되고 1번 또는 2번 쿼리를 실행할 때 3번 쿼리를 0으로 바꿔줘야 한다. 3번 쿼리 다음에 1,2번 쿼리를 실행하기 때문에 3번 쿼리를 안 바꿔도 되는 것이기 때문이다.

 

3번 쿼리에서도 만약 1,2번 쿼리에 대해서 lazytree[node]에 값이 들어 있지 않다면 3번 lazytree[node]에 xor 해주면 되지만 그렇지 않을 경우 1,2번 lazytree[node]에 xor을 해주면 된다.

그 이유는 3번도 결국 1,2번 쿼리를 합쳐 놓은 것이기 때문에 1,2번 lazytree[node]에 변화를 줘서 값을 처리할 수 있기 때문이다.

3번의 경우 tree[node]값을 (end-start+1)-tree[node]로 해주면 되고1,2번의 경우 tree[node]=lazytree[node]*(e-s+1) 해주면 된다.

 

그리고 마지막으로 mex구현은 간단하다.

위에서 A에 val이 있을 경우 1 아니면 0으로 했었기 때문에 한 구간의 값은 (end-start+1)을 넘기지 않는다.

그림으로 설명하자면

 

A, B, C, D, H, I, J, K에 순서대로 1,1,0,0,1,0,1,1 이렇게 있을 때 F는 2가 되고 E는 0, L은 1, M은 2가 되고 G는 2, N은 3, O는 5가 된다.

이때 O부터 시작했을때 O의 왼쪽 자식인 G의 값은 2이다.

이때 G의 최댓값은 4인데 G의 값은 2이다. 이뜻은 G의 자식들안에 0, 즉 start~end값중에 A수열에 포함되지 않은 수가 있다는 것이다.

그렇기 때문에 G로 내려가고 G의 왼쪽 자식인 F의 값은 2이다.

F의 최대값은 2인데 F값이 2이기 때문에 G의 왼쪽으로는 start~end 중 A에 포함되지 않은 수가 없다는 것이다.

그러므로 오른쪽으로 넘어가서 E의 왼쪽 자식이 최댓값과 동일하지 않기 때문에 왼쪽으로 내려간다 이때 start==end가 되었을 때 start값이 A수열에서 포함되지 않은 가장 작은 자연수가 되는 것이다.

 

그리고 구간 값이 (1 ≤ l ≤ r ≤ 10^18) 이기 때문에 좌표 압축을 해주면 된다.

 

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<long long>l(1000001);
ll a;
vector<ll>tree(4000000);
vector<ll>tree1(4000000);
vector<ll>tree2(4000000);
vector<ll>idx;
ll L[101000];
ll R[101000];
ll st[101000];
ll seg(ll n,ll s,ll e){
    if(s==e){return tree[n]=0;}
    return tree[n]=seg(n*2,s,(s+e)/2)+seg(n*2+1,(s+e)/2+1,e);
}
void propagate(ll n,ll s,ll e){
    if(tree1[n]==-1&&tree2[n]==0){return;}
    if(tree1[n]!=-1){
        if(s!=e){
            tree1[n*2]=tree1[n];
            tree1[n*2+1]=tree1[n];
            tree2[n*2]=0;
            tree2[n*2+1]=0;
        }
        tree[n]=tree1[n]*(e-s+1);
        //printf("%lld %lld %lld %lld\n",tree[n],n,s,e);
        tree1[n]=-1;
    }
    if(tree2[n]!=0){
        if(s!=e){
            if(tree1[n*2]==-1){
                tree2[n*2]+=1;
                tree2[n*2]%=2;
            }else{
                tree1[n*2]+=1;
                tree1[n*2]%=2;
                tree2[n*2]=0;
            }
            if(tree1[n*2+1]==-1){
                tree2[n*2+1]+=1;
                tree2[n*2+1]%=2;
            }else{
                tree1[n*2+1]+=1;
                tree1[n*2+1]%=2;
                tree2[n*2+1]=0;
            }
        }
        //printf("## %lld %lld\n",tree[n],tree2[n]);
        tree[n]=(e-s+1)-tree[n];
        //printf("# %lld %lld %lld %lld\n",tree[n],n,s,e);
        tree2[n]=0;
    }
}
void change(ll n,ll s,ll e,ll s1,ll e1,ll f){
    //printf("%lld %lld %lld\n",n,s,e);
    propagate(n,s,e);
    if(s1<=s&&e<=e1){tree1[n]=f;propagate(n,s,e);return;}
    if(e1<s||s1>e){return;}
    change(n*2,s,(s+e)/2,s1,e1,f);
    change(n*2+1,(s+e)/2+1,e,s1,e1,f);
    tree[n]=tree[n*2]+tree[n*2+1];
}
void change3(ll n,ll s,ll e,ll s1,ll e1){
    propagate(n,s,e);
    if(s1<=s&&e<=e1){tree2[n]+=1;propagate(n,s,e);return;}
    if(e1<s||s1>e){return;}
    change3(n*2,s,(s+e)/2,s1,e1);
    change3(n*2+1,(s+e)/2+1,e,s1,e1);
    tree[n]=tree[n*2]+tree[n*2+1];
}
ll qu(ll n,ll s,ll e){
    if(s==e){return s;}
    propagate(n,s,e);
    ll mid=(s+e)/2;
    propagate(n*2,s,mid);
    //printf("%lld %lld %lld\n",tree[n*2],s,mid);
    if(tree[n*2]==mid-s+1){return qu(n*2+1,mid+1,e);}else{return qu(n*2,s,mid);}
}
        
int main()
{
    ll b,c,d,q,k,gh,gk;
    scanf("%lld",&a);
    int i;
    for(i=0;i<4000000;i++){tree1[i]=-1;tree2[i]=0;}
    seg(1,0,600000);
    idx.push_back(1);
    for(i=0;i<a;i++){
        scanf("%lld %lld %lld",&st[i],&L[i],&R[i]);
        idx.push_back(L[i]);
        idx.push_back(R[i]);
        if(L[i]-1>0)idx.push_back(L[i]-1);
        if(R[i]-1>0)idx.push_back(R[i]-1);
        idx.push_back(L[i]+1);
        idx.push_back(R[i]+1);
    }
    sort(idx.begin(),idx.end());
    idx.erase(unique(idx.begin(),idx.end()),idx.end());
    for(i=0;i<a;i++){
        c=lower_bound(idx.begin(),idx.end(),L[i])-idx.begin();
        d=lower_bound(idx.begin(),idx.end(),R[i])-idx.begin();
        //printf("%lld %lld %lld\n",st[i],c,d);
        if(st[i]==1){
            change(1,0,600000,c,d,1);
        }
        if(st[i]==2){
            change(1,0,600000,c,d,0);
        }
        if(st[i]==3){
            change3(1,0,600000,c,d);
        }
        printf("%lld\n",idx[qu(1,0,600000)]);
    }
}