풀이
아이디어
문제는 단순한 세그먼트 트리 문제이기 때문에 구현만 한다면 문제가 없습니다.
세그먼트에 대해서는 나중에 더 자세히 준비해서 가지고 오겠습니다.
간략하게 세그먼트 트리를 왜 구현했는지 이야기 하자면!
-
누적합이나 누적곱을 구하기 위해서는 배열을 사용합니다.
-
하지만 중간에 값이 바뀌게 되는 경우 처음 부터 누적합이나 곱을 구해줘야 하는 어려움이 있습니다.
-
하지만 세그먼트 트리를 사용할 경우 하나의 수를 변경시 logN만큼의 변경만 하면 모든 변경이 이루어지기 때문에 편해집니다!
-
구현 방법은 트리 구현, 배열로 단순 구현이 있는데 편리를 위해 단순 배열 구현으로 문제를 풀었습니다!
상세 구현
세그먼트 트리 구현
N을 다 담을 수 있는 배열의 크기를 구해야 합니다!
배열의 크기는 2의 제곱수여야 하며 N보다 큰 최소의 수여야 합니다.
int idx = 1;
while(idx <= N) {
idx <<= 1;
}
arr = new int[idx * 2];다음과 같이 idx를 증가시켜서 idx * 2가 배열의 크기가 되도록 해줍니다.
누적 곱을 계산해야 하기 때문에 1로 초기화해줍니다.
다음과 같은 입력에 대해서 배열의 크기와 1로 초기화된 세그먼트 트리
이제 idx 부터 idx + N까지 입력을 받습니다.
st = new StringTokenizer(br.readLine());
for(int i=idx; i<idx+N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
세그먼트 트리에서 누적곱을 구하는 방법은 단순합니다! 현재 자기 idx에서 2로 나눈 값에 곱해주면 됩니다!
즉 arr[i] = arr[i * 2] arr[i 2 + 1]가 되는겁니다.
이를 반복하면 arr[1]에는 모든 누적곱들이 들어가지게 됩니다.
for(int i=idx*2-1; i>1; i--) {
arr[i/2] *= arr[i];
}
짜잔 이렇게 되면 빠르고 단순하게 누적곱을 구할 수 있습니다.
이제 다른 명령어들에 대한 처리를 해주면 문제는 해결이 됩니다.
세그먼트 트리 변경
세그먼트 트리의 i와 v를 받아서 변경을 하게 됩니다.
우리는 idx를 통해서 i를 이동시켜 idx + i로 이동하여 값을 변경해주면 됩니다.
기존의 값을 나누고 새로운 값을 곱해주는 것으로 문제를 해결하였습니다.
->나머지가 사라지는데 문제없나요?
문제에서는 정확한 값을 구하는 것이 아닌 이 값의 부호에 대해서 관심이 많기에 이 부분은 없어도 됩니다.
case 'C':
int i = Integer.parseInt(cmd[1]) - 1;
int v = Integer.parseInt(cmd[2]);
int temp = arr[idx + i];
for(int cidx = idx + i; cidx>1; cidx /= 2) {
arr[cidx] = arr[cidx] / temp * v;
}
break;위와 같이 명령어가 'C'인 경우 기존 값을 나눠주고 새로운 값을 곱하여 문제를 해결하였습니다.
C 1 10
누적곱 출력하기
l과 r을 입력받고 이제 누적곱을 구해줍니다.
만약 l이 홀수 번째라면 홀수 번째를 미리 계산하고 이동해줍니다.
만약 r이 짝수 번째라면 짝수 번째를 미리 계산하고 이동해줍니다.
case 'P':
int l = Integer.parseInt(cmd[1]) - 1 + idx;
int r = Integer.parseInt(cmd[2]) - 1 + idx;
int cp = 1;
long res = mul(l, r);
if(res == 0) {
sb.append(0);
}
else if(res < 0) {
sb.append("-");
}
else {
sb.append("+");
}
break;
}
//------------------------------
중략
//------------------------------
private static long mul(int l, int r) {
long cp = 1L;
while(l < r) {
if(l % 2 == 1) {
cp *= arr[l];
}
if(r % 2 == 0) {
cp *= arr[r];
}
l = (l+1)/2;
r = (r-1)/2;
}
if(l== r)
cp *= arr[l];
return cp;
}이를 통해서 일정 구간 사이의 누적곱을 계산할 수 있습니다!
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class No5676 {
static BufferedReader br;
static int N, K;
static int[] arr;
public static void main(String[] args) throws IOException {
br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st;
String input = "";
while((input = br.readLine()) != null) {
st = new StringTokenizer(input);
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
int idx = 1;
while(idx < N) {
idx <<= 1;
}
// System.out.println(idx);
arr = new int[idx * 2];
Arrays.fill(arr, 1);
st = new StringTokenizer(br.readLine());
for(int i=idx; i<idx+N; i++) {
int temp = Integer.parseInt(st.nextToken());
arr[i] = (temp == 0) ? 0 : (temp>0) ? 1 : -1;
}
for(int i=idx*2-1; i>1; i--) {
arr[i/2] *= arr[i];
}
// check();
for(int k=0; k<K; k++) {
String cmd[] = br.readLine().split(" ");
switch(cmd[0].charAt(0)) {
case 'C':
int i = Integer.parseInt(cmd[1]) - 1;
int v = Integer.parseInt(cmd[2]);
v = (v == 0) ? 0 : (v > 0) ? 1 : -1;
int temp = arr[idx + i];
arr[idx+i] = v;
for(int cidx = (idx + i)/2; cidx>0; cidx /= 2) {
arr[cidx] = arr[cidx * 2] * arr[cidx * 2 + 1];
}
// check();
break;
case 'P':
int l = Integer.parseInt(cmd[1]) - 1 + idx;
int r = Integer.parseInt(cmd[2]) - 1 + idx;
int cp = 1;
long res = mul(l, r);
if(res == 0) {
sb.append(0);
}
else if(res < 0) {
sb.append("-");
}
else {
sb.append("+");
}
break;
}
}
sb.append("\n");
}
System.out.println(sb);
br.close();
}
private static long mul(int l, int r) {
long cp = 1L;
while(l < r) {
if(l % 2 == 1) {
cp *= arr[l];
}
if(r % 2 == 0) {
cp *= arr[r];
}
l = (l+1)/2;
r = (r-1)/2;
}
if(l== r)
cp *= arr[l];
return cp;
}
private static void check() {
for(int a : arr) {
System.out.print(a + " ");
}System.out.println();
}
}
