[백준]가로 블록 쌓기(18407)

문제 링크 : [백준]가로 블록 쌓기(18407)

18407번: 가로 블록 쌓기

문제 설명

N개의 가로 블록이 주어집니다.

블록을 주어진 위치에 차례로 쌓았을 때, 최대 높이를 구하세요.

입력

N(블록의 갯수, 1 <= N <= 1,000,000)

W_i D_i(W_i : 블록의 길이, D_i : 블록의 위치(왼쪽에서 얼마나 떨어져있는지), 1 <= W_i,D_i <= 1,000,000,000)

5
4 2
4 6
4 5
3 1
3 3

 

출력

3

 

카테고리

#세그먼트트리 #LazyPropagation #좌표압축

 

시간 복잡도 상한

O(NlogN)

 

해결 방법

1. 현재 놓는 블록이 다른 블록 위에 올라가려면 현재 블록의 범위 안에 다른 블록이 하나라도 있어야 합니다.
2. 그리고 범위 안에 있는 블록 중 높이가 제일 높은 블록의 위로 현재 블록이 올라가게 될 것입니다.
3. 즉 이전 블록들이 쌓여있는 모양에서 현재 블록의 범위 내에 가장 높은 블록의 위치를 찾으면 됩니다.
4. 따라서 세그먼트 트리를 이용하여 구간 최대값을 찾으면 됩니다.
5. 그리고 블록이 범위로 구성되어있어 Lazy Propagation을 이용하여 업데이트하면 빠르게 구할 수 있습니다.
6. 현재 블록의 구간 내에 최대값(MaxV)을 구하여, 현재 블록 구간을 MaxV+1로 업데이트하여 최대 높이 값을 갱신합니다.
7. 마지막까지 한 후, 전체 구간 중 최대값을 출력하면 됩니다.
8. 단 블록의 범위가 최대 20억이기 때문에 세그먼트 트리를 구성하기에는 메모리가 부족합니다.
9. 블록이 최대 10만개이고, 서로 상대적인 위치만 중요하기 때문에, 좌표정보를 모아 순서대로 인덱스를 따로 따줍니다.
10. 새로 딴 인덱스는 최대 20만개이기 때문에 세그먼트 트리를 구성하는데 문제가 없습니다.

시간복잡도

O(NlogN)

코드

#include<iostream>
#include<map>
#include<algorithm>
#define N 100001
using namespace std;
int n,t[N*8],d[N*8],i,o[N][2],k;
map<int,int>m;
void z(int p,int l,int r){
    if(d[p]){
        t[p]=max(t[p],d[p]);
        if(l!=r)d[p*2]=max(d[p*2],d[p]),d[p*2+1]=max(d[p*2+1],d[p]);
        d[p]=0;
    }
}
int u(int p,int l,int r,int x,int y,int v){
    z(p,l,r);
    if(y<l||r<x)return t[p];
    if(x<=l&&r<=y)d[p]=v,z(p,l,r);
    else t[p]=max(u(p*2,l,(l+r)/2,x,y,v),u(p*2+1,(l+r)/2+1,r,x,y,v));
    return t[p];
}
int q(int p,int l,int r,int x,int y){
    z(p,l,r);
    if(y<l||r<x)return 0;
    if(x<=l&&r<=y)return t[p];
    else return max(q(p*2,l,(l+r)/2,x,y),q(p*2+1,(l+r)/2+1,r,x,y));
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    for(;i<n;i++){
        cin>>o[i][1]>>o[i][0];
        o[i][1]+=o[i][0]-1;
        m.insert({o[i][0],0});
        m.insert({o[i][1],0});
    }
    for(auto x:m)m[x.first]=++k;
    for(i=0;i<n;i++)u(1,1,k,m[o[i][0]],m[o[i][1]],q(1,1,k,m[o[i][0]],m[o[i][1]])+1);
    cout<<t[1];
}