푸으름

✏️ 문제 링크 https://www.acmicpc.net/problem/14245 14245번: XOR 첫 번째 줄에 수열의 크기 n (0 < n ≤ 500,000)이 주어진다. 두 번째 줄에 수열의 원소가 0번부터 n - 1번까지 차례대로 주어진다. 수열의 원소는 100,000보다 크지 않은 음이 아닌 정수이다. 세 번째 줄 www.acmicpc.net ✏️ 문제 설명 ✏️ 문제 풀이 느리게 갱신되는 세그먼트 트리를 이용하는 문제입니다. 백준 19975번 문제에서 XOR연산이 추가되었습니다. 느리게 갱신되는 세그먼트 트리를 구현하면서 XOR연산을 넣어주시면 됩니다. XOR기호는 ^이고, 단 갱신할려는 구간의 길이가 짝수이면 XOR연산을 해도 0이므로 구간의 길이가 홀수일 때만 XOR연산을 해주도록 설..

✏️ 문제 링크 https://www.acmicpc.net/problem/16975 16975번: 수열과 쿼리 21 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i j k: Ai, Ai+1, ..., Aj에 k를 더한다. 2 x: Ax 를 출력한다. www.acmicpc.net ✏️ 문제 설명 ✏️ 문제 풀이 이 문제 역시 느리게 갱신되는 세그먼트 트리로 구현하는 문제입니다. 여기서 조금 더 생각해 봐야 할 것은 x번째 원소를 출력하는 건데, x번째 인덱스를 구하는 과정은 이분 탐색 과정을 통해서 값을 찾아낼 수 있습니다. 아래 문제는 느리게 갱신되는 세그먼트 트리의 기본 틀을 구현한 문제입니다. https://pooreumjung.t..

✏️ 문제 링크 https://www.acmicpc.net/problem/10999 10999번: 구간 합 구하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net ✏️ 문제 설명 ✏️ 문제 풀이 세그먼트 트리의 한 종류인 느리게 갱신되는 세그먼트 트리를 구현하는 문제입니다. 구간에다가 특정 값을 더하게 되는 연산을 하게되면 일반적인 세그먼트 트리로 구현하게 되면 시간초과가 발생하게 됩니다. 이를 해결하기 위해 만들어진게 느리게 갱신되는 세그먼트 트리입니다. 특정 구간에 값을 ..

✏️ 문제 링크 https://www.acmicpc.net/problem/5676 5676번: 음주 코딩 각 테스트 케이스마다 곱셈 명령의 결과를 한 줄에 모두 출력하면 된다. 출력하는 i번째 문자는 i번째 곱셈 명령의 결과이다. 양수인 경우에는 +, 음수인 경우에는 -, 영인 경우에는 0을 출력한다. www.acmicpc.net ✏️ 문제 설명 ✏️ 문제 풀이 기본적인 세그먼트 트리 구현 문제입니다. 그냥 계산하시면 오버플로우가 발생할 수 있으니 양수일 때는 1, 0일때는 0, 음수일 때는 -1로 처리해줍니다! ✏️ 문제 코드 #include #include using namespace std; int N, K; vectorarr, tree; int l, r, index, value,a; char qu..