(백준 11505번 구간 곱 구하기 C++) 라이님 블로그 대회 알고리즘 따라잡기 12) SegmentTree 2

세그먼트 트리! 이제 쬐금 익숙해진 것 같다.

 

2042번과 매우 비슷하지만, 아직 세그먼트 트리가 익숙치 않아 푸는데 매우 매우 오래 걸렸다..^^

 

2042번 풀이는 아래에...!

https://jjo-mathstory.tistory.com/entry/%EB%B0%B1%EC%A4%80-2042%EB%B2%88-%EA%B5%AC%EA%B0%84-%ED%95%A9-%EA%B5%AC%ED%95%98%EA%B8%B0-C-%EB%9D%BC%EC%9D%B4%EB%8B%98-%EB%B8%94%EB%A1%9C%EA%B7%B8-%EB%8C%80%ED%9A%8C-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%94%B0%EB%9D%BC%EC%9E%A1%EA%B8%B0-12-SegmentTree-1

(백준 2042번 구간 합 구하기 C++) 라이님 블로그 대회 알고리즘 따라잡기 12) SegmentTree 1

 

백준 11505번 

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

#include <iostream>
#include <vector>
using namespace std;

constexpr long long MAX_N = 1000000007;

struct segTree {
	int n, start;
	vector<long long> v;

	segTree(int n) : n(n) {
		start = 1;
		while (start < n) start *= 2;
		v.resize(2 * start);
		fill(v.begin(), v.end(), 1);
	}

	void construct() {
		for (int i = start - 1; i > 0; i--)
			v[i] = ((v[i * 2] % MAX_N) * (v[i * 2 + 1] % MAX_N) % MAX_N);
	}

	void change(int a, long long b) {
		a += start; 
		v[a] = b; // ★ 값을 직접 변경
		while (a > 1) {
			a /= 2;
			v[a] = ((v[a * 2] % MAX_N) * (v[a * 2 + 1] % MAX_N)) % MAX_N;
		}
	}


	long long mul(int a, int b) { return mul(a, b, 1, 0, start) % MAX_N; }
	long long mul(int a, int b, int node, int na, int nb) {
		if (nb <= a || b <= na) return 1;
		if (a <= na && nb <= b) return v[node] % MAX_N;
		int mid = (na + nb) / 2;
		return (mul(a, b, node * 2, na, mid) % MAX_N) * (mul(a, b, node * 2 + 1, mid, nb) % MAX_N) % MAX_N;
	}
};

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int N, M, K; cin >> N >> M >> K;
	segTree st(N);
	for (int i = 0; i < N; i++) cin >> st.v[i + st.start];

	st.construct();

	for (int i = 0; i < M + K; i++) {
		int a, b; long long c;
		cin >> a >> b >> c;
		if (a == 1) st.change(b - 1, c);
		if (a == 2) cout << st.mul(b - 1, c) << "\n";
	}

}

 

https://www.acmicpc.net/board/view/112465

<< 혹시 반례가 필요하다면 요거 참고해보세용!!ㅎㅎㅎ

 

역시 큰 수는 잘 나눠야 풀 수 있쮸~?!!!