[BOJ/C++] 17353 - 하늘에서 떨어지는 1, 2, ..., R-L+1개의 별

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

---

레이지 프로파게이션 공부하다가 만난 문제입니다.

그래서 "레이지를 쓰긴 하겠구나"는 알았지만, 어떻게 레이지를 써야될 지가 막막했습니다.

도저히 고민해도 풀이가 떠오르지 않았기에, 결국 답을 봤던 문제입니다..

 

일단 Lazy Propagation은 기본적으로 두가지 연산을 지원합니다.

1. 구간에 대한 단일값 업데이트 쿼리

2. 구간에 대한 쿼리

 

하지만 문제에서 주어지는쿼리는 다음과 같습니다.

1. 구간에 대한 다중값(등차수열) 업데이트 쿼리

2. 점에 대한 쿼리

 

 

우선 구간 업데이트입니다. 

문제를 위해 구간에 대해 1,2,3,...,R-L+1씩 업데이트 해야합니다.

하지만 가지고있는 연산은 단일 값으로만 업데이트가 가능합니다.

 

그래서 처음 생각해봤던 풀이는, R-L+1번 구간 업데이트를 진행하는 것이었습니다.

구간 [L, R]에 대한 업데이트가 있다고 하면,

[L,R에 +1

[L+1,R]에 +1

[L+2,R]에 +1

...

[R,R]에 +1

 

이렇게 업데이트하면, 문제에서 주어지는 쿼리를 반영할 수는 있습니다.

하지만 이렇게 구현하면 업데이트 연산은 R-L+1번 진행하므로, 시간초과를 피할 수 없습니다.

 

또한, 문제의 점 쿼리를 처리하기 위해선 레이지의 구간쿼리는 "오버스펙"(?)입니다.

그럼 이를 오버스펙이 되지 않도록 연산을 조금 바꿀 수 있으면 좋겠습니다.

 

즉, 

[구간에 대한 단일 값 업데이트]로 [구간에 대한 다중값 업데이트]를 나타낼 수 있어야하고,

구간 쿼리가 오버스펙이 되지 않도록 점 쿼리를 표현해야합니다.

 

 

 

이제 저의 풀이입니다.

저는 imos법 + lazy Propagation을 이용하여 해결했습니다.

문제에서 요구하는 업데이트되는 값은 공차가 1인 등차수열임을 우선 관찰해야 했습니다.

 

세그먼트 트리의 값을 인덱스의 실제 "값"이 아니라, "이전 값에 대한 증가량"을 저장하게 된다면, 

구간 [L,R]에 +1씩 업데이트 하는 연산을 통해, 구간에 공차가 1인 등차수열만큼 증가함을 표현할 수 있게 됩니다.

간단하게, IMOS를 떠올리면 되겠습니다. 

 

[L,R]에 +1씩 업데이트를 진행하고, 마지막으로 점 R+1에는 (R-L+1)만큼 감소시켜주면 

최종적으로 우리가 원하는 "1. 구간에 대한 다중값(등차수열) 업데이트 쿼리를" 표현할 수 있습니다.

 

그럼 구간쿼리를 이용하여 점에대한 값을 찾아줄 수 있습니다. 

점 X에 대한 값을 구하려면, 맨 처음 인덱스부터, 점X까지의 합을 구해주면 됩니다.

 

---

코드

#include<bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define rep(i,x,y) for(int i=x;i<y;i++)
#define all(x) begin(x),end(x)
#define rall(x) rbegin(x),rend(x)
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tiii;
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
/*----------------------*/

vector<ll> seg, lazy;
ll arr[1'000'001];
void lazy_update(int idx, int st, int en){ 
    if(!lazy[idx]) return; 
    seg[idx] +=(en-st+1)*lazy[idx]; 
    if(st!=en){ 
        lazy[idx*2]+= lazy[idx]; 
        lazy[idx*2+1]+= lazy[idx]; 
    } 
    lazy[idx] = 0; 
} 
void update_range(int idx, int st, int en, int l, int r, ll val){
    lazy_update(idx,st,en);
    if(en<l||r<st) return;
    if(l<=st&&en<=r){
        seg[idx]+=(en-st+1)*val;
        if(st!=en){
            lazy[idx*2]+=val;
            lazy[idx*2+1]+=val;
        }
        return;
    }
    int mid = (st+en)/2;
    update_range(idx*2,st,mid,l,r,val);
    update_range(idx*2+1,mid+1,en,l,r,val);
    seg[idx] = seg[idx*2] + seg[idx*2+1];
}
ll lazy_query(int idx, int st, int en, int l, int r){
    lazy_update(idx,st,en);
    if(en<l||r<st) return 0;
    if(l<=st&&en<=r) return seg[idx];
    int mid = (st+en)/2;
    return lazy_query(idx*2,st,mid,l,r) + lazy_query(idx*2+1,mid+1,en,l,r);
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin>>n;
    rep(i,1,n+1) cin>>arr[i];
    
    seg.resize(4*n); lazy.resize(4*n);
    rep(i,1,n+1) update_range(1,1,n,i,i,arr[i]-arr[i-1]);

    int m; cin>>m;
    while(m--){
        int t; cin>>t;
        if(t==1){
            int l,r; cin>>l>>r;
            update_range(1,1,n,l,r,1);
            update_range(1,1,n,r+1,r+1,-(r-l+1));
        }   
        else{
            int x; cin>>x;
            cout<<lazy_query(1,1,n,1,x)<<'\n';
        }
    }
}