3차원 점과 쿼리

시간 제한7초메모리 제한1024 MB

요약
각 질의의 상자 좌표를 이전 답들의 누적 합과 XOR로 복원한 뒤, 축에 평행한 3차원 상자 안에 들어가는 점의 개수를 센다.
난이도

어려움10점 중 8점

유형
세그먼트 트리, 정렬, 이분 탐색, 누적 합
정답자
아직 제출이 없습니다

문제

3차원 공간에 주어진 N개의 점에 대해 다음 쿼리를 처리하는 프로그램을 작성하시오.

  • lx ly lz rx ry rz: 점 (lx, ly, lz)과 점 (rx, ry, rz)을 꼭짓점으로 하는 직육면체 영역에 포함된 점의 개수를 출력한다.

직육면체의 모든 모서리는 축에 평행하며, 주어지는 (lx, ly, lz)와 (rx, ry, rz)를 연결한 선분은 이 직육면체의 대각선이다.

입력

첫 번째 줄에 점의 수 N과 쿼리의 수 Q가 공백으로 구분하여 주어진다. (1 ≤ N, Q ≤ 105)

다음 N개의 줄에 걸쳐 점의 좌표를 의미하는 세 정수 x, y, z가 공백으로 구분하여 주어진다. (0 ≤ x, y, z ≤ 109)

다음 Q개의 줄에 걸쳐 6개의 정수 ai, bi, ci, di, ei, fi가 주어진다. (0 ≤ ai, bi, ci, di, ei, fi < 263)

i번째 쿼리의 lx ly lz rx ry rz는 다음과 같다.

  • lx = (ai xor Si-1) mod (109 + 1)
  • ly = (bi xor Si-1) mod (109 + 1)
  • lz = (ci xor Si-1) mod (109 + 1)
  • rx = (di xor Si-1) mod (109 + 1)
  • ry = (ei xor Si-1) mod (109 + 1)
  • rz = (fi xor Si-1) mod (109 + 1)

Si = Si-1 + ansi이며 S0는 0이다.

출력

Q개의 줄에 각 쿼리의 정답을 순서대로 출력한다.

예제1

  1. 예제 1

    입력
    5 8
1 0 5
1 1 10
5 1 10
0 10 5
2 10 0
0 0 3 5 5 8
0 0 2 6 5 6
1 1 0 2 4 11
2 2 6 7 9 4
2 3 1 0 9 4
5 4 0 14 5 14
6 6 2 1 2 14
6 7 3 15 5 0
    예상 출력
    1
0
2
0
1
3
0
1