컴퓨터하는 kimmessi

https://www.acmicpc.net/problem/2268 2268번: 수들의 합 7 첫째 줄에는 N(1 ≤ N ≤ 1,000,000), M(1 ≤ M ≤ 1,000,000)이 주어진다. M은 수행한 명령의 개수이며 다음 M개의 줄에는 수행한 순서대로 함수의 목록이 주어진다. 첫 번째 숫자는 어느 함수를 사용했는 www.acmicpc.net 문제 해결 알고리즘 세그먼트 트리 기초 문제 long long자료형을 써주고, 합을 구할 때 b와 c가 무조건 c가 크게 주어지지 않기 때문에 이 점 유의하여야한다. 소스 코드 #include #define ll long long using namespace std; const int MAX = 1000000; int N, M; ll arr[MAX+1], tr..

https://www.acmicpc.net/problem/11505 11505번: 구간 곱 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 곱을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 문제 해결 알고리즘 세그먼트 트리 문제인데, 곱이기 때문에 구간 합 구하기 문제와는 좀 다르게 update 함수를 아래부터 위로 다시 곱하는 방식으로 구해주어야한다. 왜냐면 0이 있기 때문 오버플로우가 날 수 있으므로 long long 자료형을 써야한다. 소스 코드 #include #define ll long long using nam..

https://www.acmicpc.net/problem/2357 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100 www.acmicpc.net 문제 해결 알고리즘 최댓값을 찾는 세그먼트 트리와 최솟값을 찾는 세그먼트 트리를 각각 만들어 범위내 최댓값 최솟값을 출력해준다. 소스 코드 #include using namespace std; const int MAX = 100001; int arr[MAX], minTree[4*MAX], maxTree[4*MAX]; int maxinit(int start, i..

https://www.acmicpc.net/problem/14427 14427번: 수열과 쿼리 15 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109) 2 : 수열에서 크기가 가장 작은 값의 인덱스를 www.acmicpc.net 문제 해결 알고리즘 최솟값이 있는 인덱스를 계속 업데이트해주는 세그먼트 트리를 이용해 풀 수 있는 문제 소스 코드 #include #define ll long long int using namespace std; #define MAX 100001 int N; ll arr[MAX], tree[4*MAX]; int minIndex(int x, i..