POJ - 2155 매트릭스 2 차원 트 리 배열, HDU - 3584 큐 브 3 차원 트 리 배열

2401 단어 알고리즘
Matrix 는 2 차원 사각형 범위 에서 수정 하고 단일 지점 에서 조회 해 야 하 는 문제 입 니 다.큐 브 는 3 차원 상황 에서 의 확장 이다.1 차원 구간 에서 단일 조회 모델 을 수정 하면 2 차원 으로 확장 할 수 있다.2 차원 트 리 배열 로 차이 점 의 행렬 을 유지 하고 결 과 를 구 하 는 것 이 실제 단일 요소 값 입 니 다.1 차원 상황 에서 (x, y) 구간 에 v 를 추가 하면 add (x, v) 와 add (y + 1, - v) 를 실행 할 수 있 습 니 다.2 차원 에서 (x1, y1) - (x2, y2) 사각형 범위 에 v 를 추가 하고 용 척 원 리 를 고려 하여 집행 할 수 있다.
add(x1, y1, v);
add(x1, y2 + 1, -v);
add(x2 + 1, y1, -v);
add(x2 + 1, y2 + 1, v);

3 차원 상황 에서 (x1, y1, z1) - (x2, y2, z2) 입방체 범위 에 v 를 더 하고 좀 더 복잡 하 게 그림 을 그 려 서 좀 더 고려 하면 얻 을 수 있다.
add(x1, y1, z1, v);
add(x1, y1, z2+1, -v);
add(x1, y2+1, z1, -v);
add(x2+1, y1, z1, -v);
add(x1, y2+1, z2+1, v);
add(x2+1, y1, z2+1, v);
add(x2+1, y2+1, z1, v);
add(x2+1, y2+1, z2+1, -v);

이 두 문제 의 수정 은 모두 0 과 1 사이 에 고 쳐 진 것 으로 모 2 의 의미 에서 의 가감 으로 볼 수 있다.따라서 수정 작업 은 가감 법 으로 시 뮬 레이 션 할 수 있 으 며 최종 출력 결과 모델 2 를 사용 하면 된다.
여러 조 의 배열 의 경우 매번 배열 을 리 셋 하 는 것 을 기억 하 세 요. 그렇지 않 으 면 오류 가 발생 할 수 있 습 니 다.입력 규모 범위 만 정리 할 수 있 는 배열 도 있 으 며, 매번 전체 배열 을 비우 지 않 아 도 TLE 를 피 할 수 있다.

좋은 웹페이지 즐겨찾기