IOI 2001 day1 1- 모바일(Mobile Phones) > 문제은행 : 정보올림피아드&알고리즘




1554 : 모바일(Mobile Phones)

제한시간
1000 ms   
메모리제한
64 MB   
해결횟수
2 회   
시도횟수
13 회   

문제

정올시의 4세대 이동 전화 기지국은 다음과 같은 방식으로 운영된다. 

기지국이 있는 영역들은 정사각형 칸으로 구분된다. 

정사각형들은 S*S 크기의 행렬을 이루며, 칸의 가로 세로 위치는 0부터 S-1까지 번호가 매겨져 있다. 

각 영역 안에서 볼 때, 개통중인 이동 전화의 개수는 시시각각 변할 수 있다. 

전화를 가진 사람이 다른 칸(영역)으로 이동할 수 있고, 전화기 전원을 켜거나 끌 수도 있기 때문이다. 

그런 일이 생기면 각 기지국은 자기 영역 내에서 생긴 변화를 이동전화 본부로 보고한다.

여러 기지국에서 날아오는 보고를 받아들인 뒤, 

임의의 직사각형 영역에 켜져 있는 이동 전화의 총 개수를 묻는 물음에 제대로 응답해 주는 프로그램을 작성하라.


입력형식

입력은 임의의 명령(최대 60,000개)으로 이루어진다. 

명령은 다음과 같다.

  

0 S

기지국 영역의 크기를 알려준다.

이는 각 구역의 크기를 S*S(S≤1024)로 잡고 각 구역의 개통 전화 수를 모두 0으로 초기화 하도록 하는 명령이다.

1 X Y A

X Y위치에 전화의 개수가 A개 추가되었음을 알린다. A의 값은 양수이거나 음수이다

(음수일 경우 사라진 전화의 개수를 의미한다.)

이 명령에서 추가된 전화의 개수가 정수 범위를 넘기는 경우는 없다고 가정한다.

2 L B R T

가로(L≤X≤R) 세로(B≤Y≤T)에 속하는 직사각형 영역에서 개통중인 전화의 모든 개수를 묻는다.

X와 Y는 0~S-1의 숫자이다.

3

프로그램을 종료시킨다.

  

[제약사항] 

영역의 크기는 0*0 <= S * S < 1024 * 1024 이다. 

모든 정사각형의 칸(셀)의 값 V는 항상 0 <= V <= 32767 이다. 

업데이트 값 A는 -32768 < = A <= 32767이다. 

전체 명령수 U는 3<= U <= 60002이다. 

영역 전체의 전화 대수의 총합 M은 2^30 이하이다.

 

 


출력형식

2번 명령에 대한 명령의 답을 한 줄에 하나씩 출력한다. 

질의에 대하여 230을 넘어가는 경우는 존재하지 않는다.


입력 예

0 4
1 1 2 3
2 0 0 2 2
1 1 1 2
1 1 2 -1
2 1 1 2 3
3

출력 예

3
4

Hint!

 0 4 <- 구역의 크기를 4 x 4로 맞춘다.
1 1 2 3 <- (1,2)에 전화의 개수를 3개 추가한다.
2 0 0 2 2 <- (0,0)~(2,2)에 해당하는 직사각형 영역에 존재하는 전화 수의 합을 출력한다.
1 1 1 2 <- (1,1)위치의 전화수에 2를 추가한다.
1 1 2 -1 <- (1,2)위치에 있는 전화 수에 1을 제거한다.
2




경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP