[BOJ] 6461 Hotel

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

6164번: Hotel

딱 보면 뭔가 금광세그를 박아야 할 것 같은 느낌이 든다.

그래서 한번 금광세그를 박았을때 뭘 어떻게 해야 할지를 적어보면, 

struct T {
    int lmax,rmax,amax,sum;
}t[200005];

T f(T L,T R) {
    T ret;
    ret.sum = L.sum+R.sum;
    ret.lmax = L.lmax+(L.lmax == L.sum ? R.lmax : 0);
    ret.rmax = R.rmax+(R.rmax == R.sum ? L.rmax : 0);
    ret.amax = max({L.amax,R.amax,L.rmax+R.lmax});
    return ret;
}

\(lmax\) : 구간을 기준으로 왼쪽에서 최대 몇개가 \(0\)인가

\(lmax\) : 구간을 기준으로 오른쪽에서 최대 몇개가 \(0\)인가

\(amax\) : 구간에서 가장 긴 \(0\) 부분 구간의 길이

\(sum\) : 현재 구간의 크기 (\(s~e\) 라면 \(s-e+1\))

라고 정해주면 쉽게 식이 나오는데, 그건 위의 코드를 참고하자.

 

1번 쿼리를 처리하는 경우에 대해 알아볼건데,  현재 구간의 세그 인덱스가 \(idx\)고, 구간이 \([s, e]\), \(mid = (s+e)/2\) 라고 두자.

\(tree[idx*2].amax > D\) 인 경우, \(query(idx*2,s,mid)\)를 재귀적으로 호출할 수 있다.

\(tree[idx*2].rmax+tree[idx*2+1].lmax > D\) 인 경우, \(mid-tree[idx*2].rmax+1\)가 답이다.

모두 아닌 경우, \(query(idx*2+1,mid+1,e)\)를 재귀적으로 호출할 수 있다.

 

총 시간복잡도는 \(O(QlogN)\)이다.

#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define mp make_pair
#define all(v) v.begin(),v.end()
#pragma gcc optimize("O3")
#pragma gcc optimize("Ofast") 
#pragma gcc optimize("unroll-loops")
using namespace std;
const int INF = 1e9;
const int TMX = 1 << 18;
const long long llINF = 1e18;
const long long mod = 1e9+7;
const long long hashmod = 100003;
typedef long long ll;
typedef long double ld;
typedef pair <int,int> pi;
typedef pair <ll,ll> pl;
typedef vector <int> vec;
typedef vector <pi> vecpi;
typedef long long ll;
int Q,n;
int la[200005];

struct T {
    int lmax,rmax,amax,sum;
}t[200005];

void push(int x,int l,int r) {
    if(la[x] == -1) return;
    t[x].sum = r-l+1;
    if(la[x]) t[x].lmax = t[x].rmax = t[x].amax = 0;
    else t[x].lmax = t[x].rmax = t[x].amax = r-l+1;
    if(l^r) la[x*2] = la[x*2+1] = la[x];
    la[x] = -1;
}

T f(T L,T R) {
    T ret;
    ret.sum = L.sum+R.sum;
    ret.lmax = L.lmax+(L.lmax == L.sum ? R.lmax : 0);
    ret.rmax = R.rmax+(R.rmax == R.sum ? L.rmax : 0);
    ret.amax = max({L.amax,R.amax,L.rmax+R.lmax});
    return ret;
}

void update(int x,int l,int r,int rl,int rr,int val) {
    push(x,l,r);
    if(rl > r||l > rr) return;
    if(rl <= l&&r <= rr) {
        la[x] = val;
        push(x,l,r);
        return;
    }
    int mid = (l + r) >> 1;
    update(x*2,l,mid,rl,rr,val), update(x*2+1,mid+1,r,rl,rr,val);
    t[x] = f(t[x*2],t[x*2+1]);  
}

int query(int x,int l,int r,int d) {
    push(x,l,r);
    if(l == r) return l;
    int mid = (l + r) >> 1;
    push(x*2,l,mid), push(x*2+1,mid+1,r);
    if(t[x*2].amax >= d) return query(x*2,l,mid,d);
    if(t[x*2].rmax+t[x*2+1].lmax >= d) return mid-t[x*2].rmax+1;
    return query(x*2+1,mid+1,r,d); 
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n >> Q;
    memset(la,-1,sizeof(la));
    update(1,1,n,1,n,0);
    while(Q--) {
        int op,x,y; cin >> op >> x;
        if(op & 1) {
            int wi = (t[1].amax < x ? 0 : query(1,1,n,x));
            cout << wi << '\n';
            if(wi) update(1,1,n,wi,wi+x-1,1);
        }
        else {
            cin >> y;
            update(1,1,n,x,x+y-1,0);
        }
    }
}