[백준 13925번] [Lazy propagation] 수열과 쿼리 13

Approach

현대대수나 집합론에서 다루는 것처럼, 연산 자체를 잘 정의해주면 된다.

 

궁극적으로 이 문제가 naive하게 풀기 어려운 이유는 본질적으로 연산을 함에 있어 덧셈과 곱셈 중 곱셈의 우선순위가 더 높기 때문이다.

잘 생각해보면 본질적으로 더하고 곱하는 연산은 다음과 같이 정의할 수 있다.

f : R X R X R |-> R 이다.

즉 예를 들어서 기존에 가지고 있는 값을 x, 곱하는 수를 y, 더하는 수를 z라고 하면 x * y + z로 나타낼 수 있는데, 궁극적으로 3개의 실수값을 1개의 실수값으로 대응시키는 함수를 통과시켰다고 할 수 있다.

 

이를 좀 단순하게 표현하면

$f_{a, b}(c)$ 이런 형식으로 표현할 수 있을 것이다.

 

그렇다면, 연산을 여러번 적용한다는 의미는 합성함수를 정의할 수 있냐는 것이고

결과적으로 우리가 원하는 계산은 $f_{c, d} \circ f_{a, b}(x)$를 잘 정의만 해준다. (결과적으로 수학적 귀납법에 의해서 잘 정의될 것이다.)

 

결과적으로 위의 결과로서 얻고자 하는 값은 c * (a * x + b) + d 이므로 이는 $f_{ac, cb + d}(x)$형태로 표현할 수 있다.

즉, $f_{c, d} \circ f_{a, b} = f_{ac, cb + d}$로 정의해주면 된다.

 

해당 연산의 항등원은 (1, 0)인데, 저 계산을 거쳐보면 잘 나온다. 추가적으로 교환법칙은 성립하지 않는다.

해당 내용을 이용해서 ax + b 형태의 lazy propagation을 처리해주면 된다.

Code

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)

using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
using tiii = tuple<int, int, int>;

int move_x[4] = {-1, 1, 0, 0};
int move_y[4] = {0, 0, -1, 1};
pii lazy[400000]; // value, type (type 0 : add, type 1 : multiplication)
ll seg[400000];
const ll MOD = 1000000007LL;
// 근본적으로 일반적인 세그트리로 안되는 이유가 뭘까
// 만약 lazy를 1개가 아니라 스택 형태로 주면?

void propagate(int node, int start, int end){
    if(lazy[node].first != 1 || lazy[node].second != 0){
        if(start != end){
            lazy[node * 2].first = (lazy[node * 2].first * lazy[node].first) % MOD;
            lazy[node * 2].second = (lazy[node].first * lazy[node * 2].second + lazy[node].second) % MOD;
            lazy[node * 2 + 1].first = (lazy[node * 2 + 1].first * lazy[node].first) % MOD;
            lazy[node * 2 + 1].second = (lazy[node].first * lazy[node * 2 + 1].second + lazy[node].second) % MOD;
        }
        seg[node] = ((seg[node] * lazy[node].first) % MOD + ((end - start + 1) * lazy[node].second) % MOD) % MOD;
        lazy[node] = {1, 0};
    }
}

void update(int node, int start, int end, int left, int right, ll value, ll type){
    propagate(node, start, end);
    if(end < left || right < start) return;
    if(left <= start && end <= right){
        // 단순 더하기
        if(type == 0){
            lazy[node] = {lazy[node].first, (lazy[node].second + value) % MOD};
            propagate(node, start, end);
            return;
        }
        else if(type == 1){
            lazy[node] = {(lazy[node].first * value) % MOD, (lazy[node].second * value) % MOD};
            propagate(node, start, end);
            return;
        }
        else{
            lazy[node] = {0, value};
            propagate(node, start, end);
            return;
        }
    }
    int mid = (start + end) >> 1;
    update(node * 2, start, mid, left, right, value, type);
    update(node * 2 + 1, mid + 1, end, left, right, value, type);
    seg[node] = (seg[node * 2] + seg[node * 2 + 1]) % MOD;
    return;
}

ll query(int node, int start, int end, int left, int right){
    propagate(node, start, end);
    if(end < left || right < start) return 0;
    if(left <= start && end <= right) return (seg[node]) % MOD;
    int mid = (start + end) >> 1;
    return (query(node * 2, start, mid, left, right) + query(node * 2 + 1, mid + 1, end, left, right)) % MOD;
}

int main() {
    fastio;
    memset(seg, 0, sizeof(seg));
    for(int i = 0; i < 400000; i++){
        lazy[i] = {1, 0};
    }
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++){
        ll t;
        cin >> t;
        t %= MOD;
        update(1, 1, 100000, i, i, t, 2);
    }
    int m;
    cin >> m;
    for(int i = 0; i < m; i++){
        int t;
        cin >> t;
        if(t == 1){
            ll a, b, c;
            cin >> a >> b >> c;
            c %= MOD;
            update(1, 1, 100000, a, b, c, 0);
        }
        else if(t == 2){
            ll a, b, c;
            cin >> a >> b >> c;
            c %= MOD;
            update(1, 1, 100000, a, b, c, 1);
        }
        else if(t == 3){
            ll a, b, c;
            cin >> a >> b >> c;
            c %= MOD;
            update(1, 1, 100000, a, b, c, 2);
        }
        else{
            ll a, b;
            cin >> a >> b;
            cout << query(1, 1, 100000, a, b) << "\n";
        }
    }
    return 0;
}