BOJ 14701 - 셔틀버스 (P3)

사용 알고리즘

Lazy propagation + binary search

 

풀이

학생들이 어떻게 이동하는지를 관찰해보자. 중앙을 기준으로 왼쪽에 있는 학생들은 무조건 1번 쪽으로 이동하고 오른쪽에 있는 학생들은 무조건 N번 쪽으로 이동할 것이다.

그리고 한 학생이 빠지게 되면 중간이 비고 2개의 연속된 그룹이 생기는데, 이 그룹끼리는 절대 서로 영향을 주지 않는다. (즉 한쪽 그룹에서 학생이 빠졌는데 다른 그룹의 학생이 이동하는 일은 없다는 뜻이다)

따라서 한명이 일단 빠졌다고 하자. 이 한명이 어떤 형태로 빠지는지는 N이 홀수인 경우와 짝수인 경우로 나눠 관찰하면 쉽게 찾을 수 있다.

이제 필요한 관찰은 다음과 같다.

1. 어떤 학생이 빠질 때 학생들의 번호는 항상 순서대로 유지된다.

2. 어떤 학생이 빠질 때 학생들은 항상 인접해 있다.

예를 들어 현재 '1 2 3 0 0 0 6 8' 인 상황이라고 하자. (같은 색은 같은 그룹이다)

여기서 2가 빠지면 어떻게 될까?

'1 3 0 0 0 0 6 8'이 될것이다. 1과 3의 순서가 바뀌지 않았으므로 1번 조건도 만족하고, 그룹끼리 인접해 있으므로 2번도 만족한다.

위 2개의 관찰을 기준으로 하나만 더 관찰하면 된다.

'1 2 3 4 5 6 7 8 9 0 0 0 0 ... 0 0 0'에서 0이 충분히 많다고 하고 (9개보단 많다) 4가 빠진다고 하자. 이때 1,2,3이 움직일 일은 절대 없을 것이다. 그렇다면 5 6 7 8 9는 어떻게 움직이는게 최적일까? 당연히 통째로 왼쪽으로 1칸을 이동하는 형태일 것이다. 따라서 없어지는 번호를 기준으로 그 뒷쪽이 통째로 옮겨져야 한다.

이러한 경우를 반대 그룹에서도 똑같이 생각하면 된다. 따라서 다음과 같은 처리를 할 수 있으면 된다.

1. 버스에서 x번 위치에 있는 학생의 번호를 찾는다.

2. x번인 학생이 버스에서 위치하는 번호를 찾는다.

대충 이런식의 처리를 해줄 수 있으면 위 조건에 맞춰 이분탐색으로 적절히 처리해줄 수 있다. 이렇게 처리하면 구간 갱신을 해줘야 되서 레이지 세그먼트 트리가 2개 필요하다.(학생 번호를 관리하는 세그 / 버스 위치를 관리하는 세그) 다만 알고리즘 분류에 레이지가 없는 걸로 봐서 이게 정해는 아닌 듯 하다.

#include <iostream>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <cstring>
#include <vector>
#include <string>
#include <climits>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <bitset>
#include <cassert>
#include <list>
using namespace std;
typedef long long ll;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#define MOD 998244353
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
#define inf 1e13
ll n, m;
ll g1,g2;
vector<pair<ll,ll>> qry;
struct lazyseg{
    struct Node{
        ll diff, lazy;
    };
    vector<Node> tree;
    lazyseg(): tree(4040404) {}
    void propagate(ll node, ll s, ll e){
        if(!tree[node].lazy)return;
        auto [diff, lazy] = tree[node];
        tree[node].diff += (e-s+1)*lazy;
        if(s!=e)tree[node*2].lazy += lazy, tree[node*2+1].lazy += lazy;
        tree[node].lazy=0;
    }
    void upd(ll node, ll s, ll e, ll l, ll r, ll diff){
        if(l>r)return;
        propagate(node,s,e);
        if(e<l or r<s)return;
        if(l<=s and e<=r){
            tree[node].diff += (e-s+1)*diff;
            if(s==e)return;
            tree[node*2].lazy += diff;
            tree[node*2+1].lazy += diff;
            return;
        }
        ll mid = s+e>>1;
        upd(node*2, s, mid, l, r, diff); upd(node*2+1, mid+1, e, l, r, diff);
        tree[node].diff = tree[node*2].diff+tree[node*2+1].diff;
    }
    void upd(ll l, ll r, ll diff){ upd(1,1,n,l,r,diff); }
    ll query(ll node, ll s, ll e, ll l, ll r){
        if(l>r)return 0;
        propagate(node,s,e);
        if(e<l or r<s)return 0;
        if(l<=s and e<=r)return tree[node].diff;
        ll mid = s+e>>1;
        return query(node*2,s,mid,l,r)+query(node*2+1,mid+1,e,l,r);
    }
    ll query(ll l, ll r){ return query(1,1,n,l,r); }
} seg, idxseg;
int main(){
    fast;
    cin>>n>>m;
    idxseg.upd(1,n,1);
    seg.upd(1,n,1);
    qry.resize(m);
    for(auto &[a,b] : qry)cin>>a>>b;
    ll idx = 0;
    for(; idx < m ; idx++){
        if(qry[idx].first==1){
            idxseg.upd(qry[idx].second,qry[idx].second,-1);
            if(n&1){
                bool is_L = (qry[idx].second <= n/2+1);
                if(is_L){
                    seg.upd(qry[idx].second,qry[idx].second,-1);
                    seg.upd(qry[idx].second+1, n/2+1, -1);
                    seg.upd(qry[idx].second, n/2, 1);
                    g1 = n/2, g2 = n/2+2;
                }
                else{
                    seg.upd(qry[idx].second,qry[idx].second,-1);
                    seg.upd(n/2+1,qry[idx].second-1,-1);
                    seg.upd(n/2+2,qry[idx].second,1);
                    g1 = n/2, g2 = n/2+2;
                }
            }
            else{
                bool is_L = (qry[idx].second <= n/2);
                if(is_L){
                    seg.upd(qry[idx].second,qry[idx].second,-1);
                    seg.upd(qry[idx].second+1, n/2, -1);
                    seg.upd(qry[idx].second, n/2-1, 1);
                    g1 = n/2-1, g2 = n/2+1;
                }
                else{
                    seg.upd(qry[idx].second,qry[idx].second,-1);
                    seg.upd(n/2+1,qry[idx].second-1,-1);
                    seg.upd(n/2+2,qry[idx].second,1);
                    g1 = n/2, g2 = n/2+2;
                }
            }
            break;
        }
        else cout<<qry[idx].second<<"\n";
    }
    idx++;
    for(; idx < m ; idx++){
        auto [q, num] = qry[idx];
        if(q==1){
            ll sumx = idxseg.query(1,num);
            ll l = 0, r = n+1;
            while(l+1 < r){
                ll mid = l+r>>1;
                if(sumx <= seg.query(1,mid))r = mid;
                else l = mid;
            }
            ll IDX = r; //num번 학생 위치
            idxseg.upd(num,num,-1);
            if(seg.query(1,IDX)<=g1){
                seg.upd(IDX,IDX,-1);
                seg.upd(IDX+1, g1, -1);
                seg.upd(IDX, g1-1, 1);
                g1--;
            }
            else{
                seg.upd(IDX,IDX,-1);
                seg.upd(g2,IDX-1,-1);
                seg.upd(g2+1,IDX,1);
                g2++;
            }
        }
        else{
            if(seg.query(num,num)==0){
                cout<<0<<"\n";
                continue;
            }
            ll sumx = seg.query(1,num);
            ll l = 0, r = n+1;
            while(l+1 < r){
                ll mid = l+r>>1;
                if(sumx <= idxseg.query(1,mid))r = mid;
                else l = mid;
            }
            cout<<r<<"\n";
        }
    }
}

 

어렵게 풀었는지 맞은 코드 중 코드도 긴편이고 속도도 느린 편이다.