#include #include #include using namespace std; using ull = unsigned long long; vector BiTree; int N, M, K; vector Arr; int TreeSize = 1; const int Modular = 1'000'000'007; ull MakeTree(int Index = 1) { if (Index * 2 >= BiTree.size()) { return (BiTree[Index] == 0) ? 1 : BiTree[Index]; } return BiTree[Index] = MakeTree(Index * 2) * MakeTree(Index * 2 + 1) % Modular; } ull Update(int UpdatedIndex, int Index = 1, int Start = 0, int End = TreeSize / 2 - 1) { if (Start > End || Index >= BiTree.size()) { return 1; } if (Start == End) { return BiTree[Index]; } int Mid = (Start + End) / 2; return BiTree[Index] = Update(UpdatedIndex, Index * 2, Start, Mid) * Update(UpdatedIndex, Index * 2 + 1, Mid + 1, End) % Modular; } void ChangeNum(int Index, int Value) { int i = TreeSize / 2; BiTree[i + Index] = Value; Update(Index); } ull Query(int QStart, int QEnd, int Index = 1, int Start = 0, int End = TreeSize/2 - 1) { if (Start > QEnd || End < QStart || Index >= BiTree.size()) { return 1; } if (QStart <= Start && End <= QEnd) { return BiTree[Index]; } int Mid = (Start + End) / 2; return Query(QStart, QEnd, Index * 2, Start, Mid) * Query(QStart, QEnd, Index * 2 + 1, Mid + 1, End) % Modular; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> N >> M >> K; Arr.resize(N); for (int i = 0; i < N; i++) { cin >> Arr[i]; } while (Arr.size() > TreeSize) { TreeSize <<= 1; } TreeSize <<= 1; BiTree.resize(TreeSize); for (int i = TreeSize / 2, cnt = 0; cnt < Arr.size(); i++, cnt++) { BiTree[i] = Arr[cnt]; } MakeTree(); for (int i = 0; i < M + K; i++) { int Command, Param1, Param2; cin >> Command >> Param1 >> Param2; if (Command == 1) { ChangeNum(Param1 - 1, Param2); } else { cout << Query(Param1 - 1, Param2 - 1) << "\n"; } } return 0; }

제출 #109513

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력: