[총괄] CDQ 분할 치료

전반적 으로 CDQ 분 치 는 일반 분 치 와 다른 점 은 CDQ 분 치 의 대상 이 시간 이라는 점 이다.즉, 한 시간 대 [L, R] 에 대해 우 리 는 mid = (L + R) / 2 를 취하 고 (데이터 구조 문제 로 예 를 들 어) 분 리 된 각 층 은 mid 이전의 수정 이 mid 이후 의 조회 에 기여 한 것 만 고려 한 다음 에 [L, mid], (mid, R] 로 돌아간다.
분명히 CDQ 분 치 는 오프라인 알고리즘 으로 우 리 는 모든 수정 / 조 회 를 저장 하고 함께 조작 해 야 한다.
이 동시에 CDQ 분 치 는 만족 해 야 한다. 즉, 작업 간 에 서로 독립 되 어야 한다. 즉, 하나의 작업 의 존재 가 다른 작업 의 존재 에 영향 을 주지 않 는 다 는 것 이다.
그러면 이것 은 전형 적 인 입문 문제 입 니 다. [BZOJ 1176: [Balkan 2007] Mokia]
2 차원 단점 수정, 사각형 조회.
우선 수정 / 조회 사이 의 순 서 는 시간 이 고 우 리 는 시간 에 따라 나 누 어 치료한다.
그러나 2 차원 이기 때문에 공간 을 절약 하기 위해 2 차원 의 데이터 구 조 를 열지 않 기 위해 우 리 는 처음에 모든 조작 을 x 축 에 따라 정렬 했다. 매번 처리 할 때마다 우 리 는 x 축 을 스 캔 하고 Y 축의 수정 / 조 회 를 1 차원 트 리 배열 에 넣 으 면 된다.
(또한 사각형 조 회 는 접두사 4 개 와 조회 로 나 뉜 다)
구체 적 인 절 차 는 다음 과 같다.
(1) 작업 을 오프라인 으로 내 려 놓 고 (오프라인 할 때 모든 작업 시간, 즉 작업 번호) x 축 에 따라 정렬 합 니 다. (필요 할 때 분 산 됩 니 다)
(2) 분할 구간 [L, R] (L, R 은 시간, 즉 작 동 하 는 번호) 에서 mid 를 취하 고 L 에서 R 까지 옮 겨 다 니 며 mid 이전의 수정 사항 을 1 차원 트 리 배열 에 추가 하여 mid 이후 의 조 회 를 1 차원 트 리 배열 에서 조회 합 니 다.
(3) 수정 작업 을 복원 해 야 합 니 다. L 부터 R 까지 작업 을 옮 겨 다 니 며 수정 작업 이 발생 하면 수정 작업 을 다시 합 니 다. (+ c 라면 - c)
(4) 임시 배열 을 열 고 두 개의 포인터 (한 포인터 가 왼쪽 구간 의 왼쪽 점 을 가리 키 고 다른 포인터 가 오른쪽 구간 의 왼쪽 점 을 가리 키 는 것) 를 L 에서 R 까지 옮 겨 다 니 며 mid 이전의 조작 을 왼쪽 구간 에 두 고 mid 이후 의 조작 을 오른쪽 구간 에 두 고 마지막 으로 임시 배열 에 값 을 부여 합 니 다.
(5) 귀속 [L, mid], [mid + 1, R], 귀환 (2).
귀환 의 종 착 점 은 L = = R 이다.
주의 하 세 요. 분 리 된 각 층 의 구간 에서 x 축 은 질서 가 있 습 니 다. 시간 이 순 서 롭 지 않 지만, 우 리 는 작업 을 옮 겨 다 닐 때 mid 에 따라 나 누 었 습 니 다. (이것 은 아마도 CDQ 의 분 리 를 이해 하기 어 려 운 부분 일 것 입 니 다)
코드 보 세 요.
이 문제 의 S 는 쓸모 가 없다.
또한 CDQ 분 치 는 편차 문제 도 처리 할 수 있다.
예 를 들 어 [BZOJ 3262: 낯 선 사람 에 꽃 이 피고]
n 개의 아 이 템 이 있 습 니 다. 아 이 템 마다 3 개의 속성 a, b, c 가 있 습 니 다. 아 이 템 X 에 대해 서 는 Y 만족 Xa > = Ya, Xb > = Yb, Xc > = Yc 가 있 는 지 알 아 봐 야 합 니 다. 아 이 템 Y 의 개 수 는 X 등급 입 니 다.
우 리 는 이 문제 에 시간 이 없다 는 것 을 발견 했다. 그러나 우 리 는 속성 a 를 시간 으로 바 꿀 수 있다. 예 를 들 어 시간 도 원래 순서 이다.
그래서 생각 은 a 에 따라 정렬 하고 a 번 호 를 시간 으로 하 는 것 입 니 다. 그리고 b 에 따라 정렬 합 니 다. (이해 하지 못 하면 지난 문 제 를 많이 이해 합 니 다) 그러면 우리 가 조작 할 때 1 차원 트 리 배열 에서 c 보다 작은 물건 이 얼마나 있 는 지 조회 하면 됩 니 다.
다음은 코드 (오래전) 입 니 다.
a 번호 에 주의 하 세 요.
그리고 4 차원 편차 도 있어 요.
[BZOJ 1790: [Ahoi 2008] Rectangle 사각형 보물 지]
현재 4 개의 속성 a, b, c, d 가 있 습 니 다. 아 이 템 X 에 대해 Y 만족 Xa > = Ya, Xb > = Yb, Xc < = Yc, Xd < = Yd 가 있 는 지 물 어 봅 니 다.
우 리 는 위의 문제 의 사고방식 을 따라 1 차원 을 시간 으로 삼 는 다. 그러나 여기 서 c 를 시간축 으로 선택 한 이 유 는 아래 에 있다.
c 정렬, 번호, 시간 으로 합 니 다. 그리고 d 정렬 합 니 다.
a, b 의 처리 에 대해 우 리 는 '존재 성' 만 알 면 된다 는 것 을 알 게 되 었 습 니 다. 그러면 물품 X 에 대해 우 리 는 [1, Xa] 에서 물품 Y 만족 Xb > = Yb 를 찾 아야 합 니 다. 이것 은 RMQ 문제 입 니 다. 우 리 는 선분 트 리 로 유지 해 야 합 니 다.
즉, a 를 선분 트 리 의 아래 표 시 를 하고 b 를 선분 트 리 의 가중치 로 하 며 선분 트 리 유지 구간 의 최소 값 입 니 다.
코드
c 를 왜 시간 으로 생각 하 는 지 돌 이 켜 보 자.
만약 우리 가 a 를 시간 으로 삼 아 b 를 정렬 한다 면, 우 리 는 [XC, inf) 에서 Y 가 Xd < = Yd 를 만족 시 킬 수 있 는 지 를 찾 아야 한다. 이것 은 너무 복잡 하 다. inf 는 매우 클 수 있다. 이산 화 되 더 라 도 상수 가 비교적 클 것 이다.
또 하나의 문 제 는 Mokia 와 마찬가지 로 데이터 범위 가 더 작 으 니 CDQ 분 치 를 위 한 연습 으로 하 자.
[BZOJ 2683: 간단 한 문제!]