Plite
전자오락 공방
Plite
전체 방문자
오늘
어제
  • 분류 전체보기 (274)
    • 프로젝트 (18)
      • 완성 프로젝트 (3)
      • 프로젝트 진행 내역 (15)
    • 공부 및 정리 (241)
      • 백준 코드 (222)
      • C++ (8)
      • DirectX (2)
      • Unreal Engine (6)
      • 프로그래밍 패턴 (3)
    • 기타 (12)
      • 기타 주저리 (10)
    • 게임과 취미 (1)
    • 대문 (1)

블로그 메뉴

  • 홈
  • 프로젝트
  • 취미, 일상
  • 백준 프로필

공지사항

  • [Read Me]
  • 제 블로그에 방문하신 것을 환영합니다.

인기 글

태그

  • 구현
  • 수학
  • 세그먼트 트리
  • 스택
  • 우선순위큐
  • 이분탐색
  • 백준
  • 백트래킹
  • 문자열
  • 최소 스패닝 트리
  • 분할정복
  • 트리
  • 그래프
  • 트라이
  • 누적합
  • KMP
  • 정수론
  • LCA
  • 동적계획법
  • 정렬
  • 유니온 파인드
  • 큐
  • 투포인터
  • 위상 정렬
  • SCC
  • UC++
  • 기하
  • C++
  • 브루트포스
  • 조합론

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
Plite

전자오락 공방

[C++]백준 - 11505번 문제
공부 및 정리/백준 코드

[C++]백준 - 11505번 문제

2021. 11. 1. 18:01

11505번: 구간 곱 구하기 (acmicpc.net)

 

11505번: 구간 곱 구하기

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 곱을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄

www.acmicpc.net

 

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로 나눈 나머지를 출력한다.

 


 

생각해 볼 점


2042번 문제와 동일하되, 몇가지 차이점이 있습니다.

 

1. 나머지 정리

 

- (A % X) * (B % X) == (A * B) % X 임을 이용해야 합니다.

 

따라서, 모든 노드에 1000000007로 나누고 남은 나머지를 넣어줍니다.

 

2. swap 함수

 

- 이번에는 지난번 처럼 스왑함수를 만들어 적용할 수 없습니다.

 

정직하게 쿼리문과 동일한 양식으로 swap될 index의 노드를 포함한 모든 요소를 바꾸어줍니다.

 

코드


#include <iostream>
using namespace std;
typedef long long LL;
#define MOD 1000000007

//구간합 쿼리
LL query(LL seg[], int s, int e, int node, int left, int right)
{
    if(e < left || right < s) return 1;
    if(e <= right && left <= s) return seg[node];
    
    int mid = (s + e) >> 1;
    return (query(seg, s, mid, node * 2 + 1, left, right) * 
           query(seg, mid + 1, e, node * 2 + 2, left, right)) % MOD;
}


//세그먼트 트리 B 위치의 요소를 변경
LL swap(LL arr[], LL seg[], int s, int e, int node, int b, LL c)
{
    if(b < s || e < b) return seg[node];
    if(s == e)  return seg[node] = c;
    int mid = (s + e) >> 1;
    return seg[node] = (swap(arr, seg, s, mid, node * 2 + 1, b, c) *
                        swap(arr, seg, mid + 1, e, node * 2 + 2, b, c)) % MOD;
}

//세그먼트 트리 생성
LL make_seg(LL arr[], LL seg[], int s, int e, int node)
{
    if(s == e) return seg[node] = arr[s];

    int mid = (s + e) >> 1;
    return seg[node] = (make_seg(arr, seg, s, mid, node * 2 + 1) *
                       make_seg(arr, seg, mid + 1, e, node * 2 + 2)) % MOD;
}


int main()
{
    int N, M, K;
    scanf("%d %d %d", &N, &M, &K);
    
    LL *arr = new LL[N];
    LL *seg = new LL[N << 2];
    for(int i = 0; i < N; i++) scanf("%lld", &arr[i]);
    
    make_seg(arr, seg, 0, N - 1, 0);
    
    for(int i = 0; i < M + K; i++)
    {
        int a, b;
        LL c;
        scanf("%d %d %lld", &a, &b, &c);
        if(a == 1) swap(arr, seg, 0, N - 1, 0, --b, c);
        else printf("%lld\n", query(seg, 0, N - 1, 0, --b, --c));
    }
    delete[] arr;
    delete[] seg;
	return 0;
}

 

그 외


 

저작자표시 (새창열림)

'공부 및 정리 > 백준 코드' 카테고리의 다른 글

[C++]백준 - 1311번 문제  (0) 2021.11.03
[C++]백준 - 2357번 문제  (0) 2021.11.03
[C++]백준 - 2042번 문제  (0) 2021.11.01
[C++]백준 - 2252번 문제  (0) 2021.10.31
[C++]백준 - 1173번 문제  (0) 2021.10.30
    '공부 및 정리/백준 코드' 카테고리의 다른 글
    • [C++]백준 - 1311번 문제
    • [C++]백준 - 2357번 문제
    • [C++]백준 - 2042번 문제
    • [C++]백준 - 2252번 문제
    Plite
    Plite
    개발 일지, 게임 이야기 등을 적어두는 공간입니다.

    티스토리툴바