BOJ 13925 | 수열과 쿼리 13

길이가 N인 수열에서 4가지 쿼리를 적절하게 처리하는 문제입니다.
구간 덧셈, 구간 곱셈, 구간 변경 연산과 구간 합을 출력하는 쿼리가 들어있습니다.

구간 덧셈과 곱셈, 그리고 변경은 전부 update() 연산이고, lazy하게 처리하는 방법이 조금 떠올리기 어렵습니다.
그러나 그건 tree[node] += lazy[node] 같이 단순히 레이지 값을 더하거나 곱하는 방법으로만 세그먼트 트리를 작성해봐서 그렇습니다. lazy 값을 관리하고, 적용하는 다양한 방법을 연습해보고 이 문제에 도전하시는 것을 추천드립니다.

해결 방법

어떤 노드가 push() 될 때, 그 노드는 레이지 값을 반영합니다. 덧셈 쿼리로 인한 lazy와 곱셈 쿼리로 인한 lazy가 겹쳐서 반영된 상태에서 올바르게 처리하려면 어떻게 lazy 값을 관리해야 할까요?

어떤 형태로 쿼리가 들어오든, 모든 상황은 ax+b 형태의 일차식에서 벗어나지 않습니다.

덧셈 쿼리가 들어오면 x에서 x+p가 되고, 그 후 곱셈 쿼리가 들어오면 q(x+p)가 됩니다.

곱셈 쿼리는 ax+b 형태 전체에 들어온 값 v를 곱해주게 되므로 a와 b 값 모두에 영향을 미치고, 덧셈 쿼리는 들어온 값 v를 더해주게 되므로 b에만 영향을 미칩니다.

따라서 lazy 값 두개를 관리하고, 쿼리를 처리하면 됩니다.

덧셈 쿼리는 lazy_b[node] += v 가 되고,
곱셈 쿼리는 lazy_a[node] *= v, lazy_b[node] *= v 가 됩니다.

3번 쿼리인 변경 쿼리는 a = 0, b = v로 업데이트 해주면 처리할 수 있습니다.

주의할 점은 구간 합 세그먼트 트리를 구성해야 하므로 tree[node]가 어떻게 업데이트되어야 하는 지 잘 생각해야 합니다.

tree[node]는 구간 [s, e]의 합이고, lazy_a 값은 [s, e]에 곱해지는 값이므로 tree[node]에 그대로 곱하면 됩니다.

그러나 lazy_b 값은 구간 [s, e]에 모두 더해지는 수이므로 tree[node]에 업데이트 할 때 그 구간의 길이를 곱해서 더해야 합니다.

이 부분이 틀리기 쉬우므로 코드를 작성할 때 주의해야 합니다.
그리고 자식 노드로 전파할 때 lazy_b에도 lazy_a 값을 곱해주는 것을 잊지 말도록 합시다.

코드

//#pragma GCC optimize("O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
constexpr bool local = true;
#else
constexpr bool local = false;
#endif

#define ll long long
#define pll pair<ll, ll>
#define FASTIO ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);

#define debug if constexpr (local) std::cout
#define endl '\n'

const int MOD = 1e9+7;

class SegTree{
private:
	vector<ll> tree;
	vector<ll> la;
	vector<ll> lb;
public:
	SegTree(int N){
		tree.resize(N*4);
		la.resize(N*4);
		lb.resize(N*4);
		for (auto &i: la) i = 1;
	}
	
	ll init(vector<ll> &nums, ll node, ll s, ll e){
		if (s == e) return tree[node] = nums[s];
		
		return tree[node] = (init(nums, node*2, s, (s+e)/2) + init(nums, node*2+1, (s+e)/2+1, e))%MOD;
	}
	
	void update_sum(ll node, int s, int e, int l, int r, ll v){
		push(node, s, e);
		if (e < l || r < s) return; // break condition
		if (s >= l && e <= r){ // tag condition
			lb[node] = (lb[node] + v) % MOD;
			push(node, s, e);
			return;
		}
		
		update_sum(node*2, s, (s+e)/2, l, r, v);
		update_sum(node*2+1, (s+e)/2+1, e, l, r, v);
		tree[node] = (tree[node*2] + tree[node*2+1]) % MOD;
	}
	
	void update_mul(ll node, int s, int e, int l, int r, ll v){
		push(node, s, e);
		if (e < l || r < s) return; // break condition
		if (s >= l && e <= r){ // tag condition
			lb[node] = (lb[node] * v) % MOD;
			la[node] = (la[node] * v) % MOD;
			push(node, s, e);
			return;
		}
		
		update_mul(node*2, s, (s+e)/2, l, r, v);
		update_mul(node*2+1, (s+e)/2+1, e, l, r, v);
		tree[node] = (tree[node*2] + tree[node*2+1]) % MOD;
	}
	
	void update_sudo(ll node, int s, int e, int l, int r, ll v){
		push(node, s, e);
		if (e < l || r < s) return; // break condition
		if (s >= l && e <= r){ // tag condition
			lb[node] = v;
			la[node] = 0;
			push(node, s, e);
			return;
		}
		
		update_sudo(node*2, s, (s+e)/2, l, r, v);
		update_sudo(node*2+1, (s+e)/2+1, e, l, r, v);
		tree[node] = (tree[node*2] + tree[node*2+1]) % MOD;
	}
	
	void push(ll node, ll s, ll e){
		if (la[node] == 1 && lb[node] == 0) return;
		
		tree[node] = ( ( (la[node] * tree[node]) % MOD ) + ((e-s+1) * lb[node]) % MOD ) % MOD;
		if (s != e){
			la[node*2] = (la[node*2] * la[node]) % MOD;
			lb[node*2] = (lb[node*2] * la[node]) % MOD;
			la[node*2+1] = (la[node*2+1] * la[node]) % MOD;
			lb[node*2+1] = (lb[node*2+1] * la[node]) % MOD;
			
			lb[node*2] = (lb[node] + lb[node*2]) % MOD;
			lb[node*2+1] = (lb[node] + lb[node*2+1]) % MOD;
		}
		la[node] = 1;
		lb[node] = 0;
	}
	
	ll query(ll node, int s, int e, int l, int r){
		push(node, s, e);
		if (s > r || l > e) return 0;
		if (l <= s && e <= r) return tree[node];
		
		return (query(node*2,s,(s+e)/2,l,r) + query(node*2+1,(s+e)/2+1,e,l,r)) % MOD;
	}
	
	void print_leaf_nodes(ll node, int s, int e) {
		push(node, s, e);
	    if (s == e) {
	        cout << "Leaf node at position " << s << ": " << tree[node] << endl;
	        return;
	    }
	    
	    int mid = s + e >> 1;
	    print_leaf_nodes(node * 2, s, mid);
	    print_leaf_nodes(node * 2 + 1, mid + 1, e);
	}
	
};

int main(){
	FASTIO;
	int N, Q; cin >> N;
	vector<ll> a; a.push_back(0);
	
	for (int i = 0; i < N; i++){
		int t; cin >> t;
		a.push_back(t);
	}
	SegTree SG(N);
	SG.init(a, 1, 1, N);
	
	cin >> Q;
	
	for (int i = 0; i < Q; i++){
		ll o, x, y; cin >> o >> x >> y;
		if (o == 1){
			ll v; cin >> v;
			SG.update_sum(1, 1, N, x, y, v);
		}
		else if (o == 2){
			ll v; cin >> v;
			SG.update_mul(1, 1, N, x, y, v);
		}
		else if (o == 3){
			ll v; cin >> v;
			SG.update_sudo(1, 1, N, x, y, v);
		}
		else{
			cout << SG.query(1, 1, N, x, y) << endl;
			//SG.print_leaf_nodes(1, 1, N);
		}
	}
}