BOJ 17668(시험)풀이

https://www.acmicpc.net/problem/17668

17668번: 시험

이 문제 세그 스위핑이라는 방법이 있다고는 하지만 그 방법이 아닌 2차원 머지 소트 트리를 박는 방법으로 했다.

방법은 생각보다 간단한다.

A에서 이분 탐색을 해 입력값 이상인 값들의 위치에 있는 B에서 이분 탐색을 또 하고 거기서도 이상인 값들의 위치 중 합이 입력값 이상인 값을 찾아주면 된다.

말만 간단한거 같지만 이 방법을 그대로 머지 소트 트리에 해주면 된다.

일단 A는 머지소트 트리를 사용하지 않아도 입력을 받아 정렬한 뒤 lower_bound를 구해주면 된다.

그다음 B부터는 머지소트 트리를 써줘야 한다.

A를 정렬했을 때의 위치대로 머지 소트 트리를 구현해준다. 쉽게 말하면 A값과 같이 있는 B를 정렬했을 때의 순서대로 머지 소트 트리에 넣어주면 된다.

이제 C만 만들어 주면 되는데 C는 위에서 만든 머지 소트 트리에서 각 노드당 머지 소트 트리를 하나 더 만들어 준다.

그림이 좀 이상하긴 하지만 이렇게 모든 노드에다가 또 다른 트리들을 만들어 주면 된다. 이 트리에는 합을 판별하기 위한 머지 소트 트리가 들어간다.

B에서 lower_bound를 했을 때 나온 값의 위치부터 끝까지를 C를 저장한 배열에서 탐색을 해준다. C를 저장한 머지 소트 트리는 B를 추가한 순서대로 추가해준다.

void up(ll n,ll s,ll e){
    if(s==e){
        tree[n].push_back({ip[s-1].second,ip[s-1].first+ip[s-1].second});
        pst[n].resize((e-s+1)*4,{});
        pup(1,1,e-s+1,n);
        return;}
    ll l=0,r=0,m=(s+e)/2;
    up(n*2,s,m);
    up(n*2+1,m+1,e);
    while(l<(m-s+1)&&r<(e-m)){
        if(tree[n*2][l].first<tree[n*2+1][r].first){tree[n].push_back(tree[n*2][l]);l++;
        }else if(tree[n*2][l].first>tree[n*2+1][r].first){tree[n].push_back(tree[n*2+1][r]);r++;
        }else{
            if(tree[n*2][l].second<tree[n*2+1][r].second){tree[n].push_back(tree[n*2][l]);l++;
            }else if(tree[n*2][l].second>tree[n*2+1][r].second){tree[n].push_back(tree[n*2+1][r]);r++;
            }else{tree[n].push_back(tree[n*2][l]);tree[n].push_back(tree[n*2+1][r]);l++;r++;}
        }
    }
    //printf("#%lld %lld\n",s,e);
    //for(int i=0;i<tree[n].size();i++)printf("%lld ",tree[n][i].first);
    //printf("\n");
    while(l<m-s+1){tree[n].push_back(tree[n*2][l]);l++;}
    while(r<(e-m)){tree[n].push_back(tree[n*2+1][r]);r++;}
    //printf("%lld %lld\n",s,e);
    //for(int i=0;i<tree[n].size();i++)printf("%lld ",tree[n][i].first);
    //printf("\n");
    pst[n].resize((e-s+1)*4,{});
    pup(1,1,e-s+1,n);
    
}

이게 B에 대한 머지 소트 트리 코드이다.

밑에 pst [n]라는 배열을 C에 대한 머지 소트트리 크기에 맞게 바꿔주고 값을 채워 주면 된다.

void pup(ll n,ll s,ll e,ll i){
    //printf("%lld %lld\n",i,n);
    if(s==e){pst[i][n].push_back(tree[i][s-1].second);return;}
    ll l=0,r=0,m=(s+e)/2;
    pup(n*2,s,m,i);
    pup(n*2+1,m+1,e,i);
    while(l<(m-s+1)&&r<(e-m)){
        if(pst[i][n*2][l]<pst[i][n*2+1][r]){pst[i][n].push_back(pst[i][n*2][l]);l++;
        }else if(pst[i][n*2][l]>pst[i][n*2+1][r]){pst[i][n].push_back(pst[i][n*2+1][r]);r++;
        }else{pst[i][n].push_back(pst[i][n*2][l]);pst[i][n].push_back(pst[i][n*2+1][r]);l++;r++;}
    }
    while(l<m-s+1){pst[i][n].push_back(pst[i][n*2][l]);l++;}
    while(r<(e-m)){pst[i][n].push_back(pst[i][n*2+1][r]);r++;}
}

C에 대한 머지 소트 트리 코드는 이렇게 된다.

이렇게 해주면 모든 머지 소트 트리의 구현은 끝났다.

X, Y, Z를 입력받으면서 lower_bound를 구해서 개수를 세주면 된다.

scanf("%lld %lld",&n,&m);
	for(int i=1; i<=n; i++){
        scanf("%lld %lld",&c,&d);
        ip.push_back({c,d});
		//update(1,i,1,n,{c,d});
        //suupdate(1,i,1,n,c+d);
	}
    sort(ip.begin(),ip.end());
    //for(int i=0;i<n;i++)printf("%lld %lld\n",ip[i].first,ip[i].second);
    up(1,1,n);
    for(int i=0;i<m;i++){
        scanf("%lld %lld %lld",&a,&b,&c);
        ll zx=flb(a);
       // printf("#%lld\n",zx);
        if(zx==n)printf("0\n");
        else{
            printf("%lld\n",get(1,1,n,zx+1,n,b,c));
        }
    }

ll get(ll n,ll s,ll e,ll lt,ll rt,ll x,ll x1){
    if(rt<s||lt>e)return 0;
    if(lt<=s&&e<=rt){
        ll va=slb(x,e-s+1,n);
        //for(int i=0;i<tree[n].size();i++)printf("%lld ",tree[n][i]);
        //printf("\n");
        //printf("##%lld %lld %lld\n",va,s,e);
        if(va==e-s+1)return 0;
        else return get1(1,1,e-s+1,va+1,e-s+1,x1,n);
    }
    ll mid=(s+e)/2;
    return get(n*2,s,mid,lt,rt,x,x1)+get(n*2+1,mid+1,e,lt,rt,x,x1);
}

ll get1(ll n,ll s,ll e,ll lt,ll rt,ll x,ll i){
    if(rt<e||lt>e)return 0;
    if(lt<=s&&e<=rt){
        ll er=llb(x,pst[i][n].size(),n,i);
        //printf("###%lld %lld %lld\n",er,s,e);
        return (e-s+1)-er;
    }
    ll mid=(s+e)/2;
    return get1(n*2,s,mid,lt,rt,x,i)+get1(n*2+1,mid+1,e,lt,rt,x,i);
}

여기서 llb, slb, flb는 lower_bound를 구해주는 함수이다. 이렇게 해주면 끝이 난다.