#include using namespace std; typedef long long int lld; const lld MOD = 1000000007; lld N, M, K; vector V(1000001, 1); lld pow(lld a, lld e) { if (a == 0) return 0; else if (a == 1) return 1; lld acc = a, res = 1; while (e > 0) { if (e % 2 == 1) res = (res * acc) % MOD; acc = (acc * acc) % MOD; e /= 2; } return res; } struct Node { lld value; // 노드에 포함된 값 Node *left, *right; int start, end; // 노드가 포함하느 구간 정보 Node(lld v, int s, int e): value(v), start(s), end(e), left(nullptr), right(nullptr) {} ~Node() { if (left) delete left; if (right) delete right; } // 구간 곱 [s, e]를 구함 lld product(int s, int e) { // Assert start <= s <= e <= end; int mid = (start + end) / 2; // 구하고자 하는 구간과 노드의 구간이 일치할 경우 if (start == s && end == e) return value; // 구하고자 하는 구간이 mid를 기준으로 걸쳐있는 경우 if (s <= mid && mid + 1 <= e) { return ( (left->product(s, mid) % MOD) * (right->product(mid + 1, e) % MOD) ) % MOD; } else if (e <= mid) { // 구하고자 하는 구간이 mid보다 왼쪽에 있을 경우 return left->product(s, e) % MOD; } else { // 구하고자 하는 구간이 mid + 1보다 오른쪽에 있을 경우 return right->product(s, e) % MOD; } } // idx번째 값을 v로 바꾸어줌 lld update(lld v, int idx) { if (idx < start || end < idx) return value; else if (start == idx && idx == end) { value = v; return v; } else return value = ( (left->update(v, idx) % MOD) * (right->update(v, idx) % MOD) ) % MOD; } }; // 구간 곱[start, end]에 대한 정보(start와 end 포함)를 담는 노드 생성 Node *construct(int start, int end) { lld value = (V[end] * pow(V[start - 1], MOD - 2)) % MOD; Node *node = new Node(value, start, end); // 단일 구간일 경우 left, right를 초기화 하지 않음 if (start == end) return node; int mid = (start + end) / 2; node->left = construct(start, mid); node->right = construct(mid + 1, end); return node; } int main() { cin.tie(NULL); cin.sync_with_stdio(false); cin >> N >> M >> K; lld prod = 1, a, b, c; for(int i = 1; i <= N; i++) { cin >> a; prod = (prod * a) % MOD; V[i] = prod; } Node *root = construct(1, N); M += K; while (M--) { cin >> a >> b >> c; if (a == 1) root->update(c, b); else cout << root->product(b, c) << '\n'; } return 0; }

제출 #13647

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: