[백준] 11505 구간 곱 구하기 (복습)

문제

어떤 N개의 수가 주어져 있다. 그런데 중간에 수의 변경이 빈번히 일어나고 그 중간에 어떤 부분의 곱을 구하려 한다. 만약에 1, 2, 3, 4, 5 라는 수가 있고, 3번째 수를 6으로 바꾸고 2번째부터 5번째까지 곱을 구하라고 한다면 240을 출력하면 되는 것이다. 그리고 그 상태에서 다섯 번째 수를 2로 바꾸고 3번째부터 5번째까지 곱을 구하라고 한다면 48이 될 것이다.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 곱을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄까지 N개의 수가 주어진다. 그리고 N+2번째 줄부터 N+M+K+1 번째 줄까지 세 개의 정수 a,b,c가 주어지는데, a가 1인 경우 b번째 수를 c로 바꾸고 a가 2인 경우에는 b부터 c까지의 곱을 구하여 출력하면 된다.

입력으로 주어지는 모든 수는 0보다 크거나 같고, 1,000,000보다 작거나 같은 정수이다.

출력

첫째 줄부터 K줄에 걸쳐 구한 구간의 곱을 1,000,000,007로 나눈 나머지를 출력한다.

 

세그먼트 트리 문제입니다.

부분 수열에 대한 쿼리값을 구해야합니다.

 

자료없이 혼자 작성했습니다 오타때문에 조금 고생했지만(왜 오타가있는데 테케는 통과하는거야?)

그래도 세그트리를 드디어 제대로 이해한 것 같습니다

 

기본구조가 DFS 재귀 분할정복입니다.

재귀함수 작성하는 실력이 조금은 는듯한 기분?

#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL)
#define mset(v) memset(v,0,sizeof(v));
#define rep(i,a) for(int i=0;i<a;++i)
#define REP(i,a) for(int i=1;i<=a;++i)

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int>ti;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
int dy[] = { -1,0,1,0 }, dx[] = { 0,1,0,-1 };
ll di= 1000000007;	
ll N, M, K, a[1000001], seg[4000004];

ll init(ll l,ll r,ll n) {
	if (l == r)return seg[n] = a[l] % di;
	ll mid = (l + r) / 2;
	return seg[n] = (init(l, mid, n * 2)%di * init(mid + 1, r, n * 2 + 1)%di) % di;		
}
ll update(ll l, ll r, ll n, ll t,ll v) {
	if (l <= t && t <= r) {
		if (l == r)return seg[n] = v;
		ll mid = (l + r) / 2;
		return seg[n] = (update(l, mid, n * 2, t, v) % di * update(mid + 1, r, n * 2 + 1, t, v ) %di) % di;
	}
	return seg[n] % di;
}
ll sum(ll l,ll r,ll n,ll f,ll t) {
	if (r < f || t < l)return 1; //아예 안겹치면 1
	if (f <= l && r <= t)return seg[n]%di; //완전 겹치면
	ll mid = (l + r) / 2;
	return (sum(l, mid, n * 2, f, t) % di * sum(mid + 1, r, n * 2 + 1, f, t) % di) % di;
}
int main() {
	FAST;
	cin >> N >> M >> K;
	REP(i, N)cin >> a[i];
	init(1,N,1);
	ll x, y, z;
	rep(i, M + K) {
		cin >> x >> y >> z;
		if (x == 1) {
			update(1, N, 1, y,z);
			a[y] = z;
		}
		else {
			cout << sum(1,N,1,y,z) << "\n";
		}
	}
}

 

 

함수로는 init ,sum, update가 있습니다.

update함수를 작성할때 주의할 점이, 만약 어느 배열값이 0이 되버리면, 그 위의 세그값들이 0으로 바뀌기 때문에

아래노드의 정보를 잃어버립니다.....

따라서 update함수도 좌우 자식노드에대해 재귀를 수행했습니다.

void update(ll l, ll r, ll n, ll t,ll v) {
	if (l <= t && t <= r) {
		ll mid = (l + r) / 2;
		seg[n] = seg[n] / a[t] * v;
		if (l == r)return;
		update(1, mid, n * 2, t, v);
		update(mid + 1, r, n * 2+1, t, v);
	}
}j

이렇게 작성하니 seg값이 0인경우 틀립니다.