격자 쿼리
시간 제한4초메모리 제한1024 MB
200000 곱하기 200000 격자에 N번의 직사각형 덧셈 갱신과 Q번의 직사각형 합 질의를 처리한 뒤, 모든 질의 답을 XOR해 출력한다.
문제
세로 200000, 가로 200000 크기이고 모든 값이 0으로 채워진 2차원 배열이 있다. 이 배열에서 행 번호는 아래로 갈수록, 열 번호는 오른쪽으로 갈수록 증가한다. i번째 행, j번째 열에 해당하는 위치를 (i,j)로 쓴다.
종영이는 여러분이 고통받는 모습을 보려고 N번, (X1,Y1)과 (X2,Y2) 사이의 모든 위치의 값에 V를 더하는 업데이트 연산을 했다.
여러분은 Q번, (X1,Y1)과 (X2,Y2) 사이의 모든 위치의 값의 합을 구하는 쿼리를 수행해야 한다.
입력
첫 줄에 N과 Q가 주어진다. (1 ≤ N, Q ≤ 2.5×105)
N개의 줄에 걸쳐 종영이의 업데이트에 해당하는 X1, Y1, X2, Y2, V가 순서대로 주어진다. (1 ≤ X1 ≤ X2 ≤ 2×105, 1 ≤ Y1 ≤ Y2 ≤ 2×105, 1 ≤ V ≤ 10)
그다음 Q개의 줄에 걸쳐 쿼리에 해당하는 X1, Y1, X2, Y2가 순서대로 주어진다. (1 ≤ X1 ≤ X2 ≤ 2×105, 1 ≤ Y1 ≤ Y2 ≤ 2×105)
출력
모든 쿼리의 답을 XOR한 값 하나를 출력한다. 이는 C, C++에서 ^ 연산자로 표현된다. XOR 연산자의 뜻은 이 문제를 해결하는 것과 아무 연관이 없다.