토끼
시간 제한2초메모리 제한128 MB
매일 구간에 사탕을 나눠주면서 블록 컵과 개별 상자에 성냥을 추가하는 스퀘어루트 분할 구조에서, 그날 새로 증가한 값들의 합을 구하는 문제입니다.
문제
농장에는 1번부터 N번까지 번호가 붙은 토끼 N마리가 있다. 농장 주인은 매일 딸기 몇 개를 사서 연속한 번호의 토끼들에게 한 개씩 준다.
각 토끼가 지금까지 먹은 딸기의 수를 기록하기 위해, 모든 토끼에게 빈 성냥갑이 하나씩 있다. 성냥갑은 한 줄로 놓여 있다. K^2 <= N을 만족하는 가장 큰 정수 K를 고른다. 첫 번째 성냥갑부터 차례대로 연속한 K개씩 묶어 블록을 만든다. 마지막 블록은 성냥갑이 K개보다 적을 수 있다. 각 블록 앞에는 컵이 하나 놓여 있다.
어느 날 딸기 S개를 사고 A번 토끼부터 나누어 주면, A번, A+1번, ..., A+S-1번 토끼가 각각 딸기 한 개를 받는다.
딸기를 준 뒤에는 다음 방식으로 성냥을 하나씩 기록한다.
- 어떤 블록의 모든 성냥갑이 그날 딸기를 받은 토끼에 해당하면, 그 블록의 컵에 성냥을 하나 넣는다.
- 그렇지 않으면, 그 블록 안에서 딸기를 받은 각 토끼의 성냥갑에 성냥을 하나씩 넣는다.
각 토끼가 지금까지 먹은 딸기의 수는 자기 성냥갑에 들어 있는 성냥 수와 자신이 속한 블록의 컵에 들어 있는 성냥 수의 합으로 알 수 있다.
아래 그림은 블록의 배치와 한 번의 기록 과정을 보여 준다.
토끼의 수 N과 M일 동안의 딸기 배분 방법이 주어진다. 각 날마다, 그날 성냥을 넣은 모든 성냥갑과 컵에 현재 들어 있는 성냥 수의 합을 구하시오.
입력
첫째 줄에 N과 M이 공백으로 구분되어 주어진다.
- 1 <= N, M <= 100000
다음 M개 줄에는 그날 산 딸기의 수 S와 딸기를 주기 시작하는 토끼의 번호 A가 주어진다.
- 1 <= A <= N
- 1 <= A+S-1 <= N
출력
M개의 수를 출력한다. k번째 줄에는 k번째 날에 성냥을 넣은 성냥갑과 컵에 현재 들어 있는 성냥 수의 합을 출력한다.
힌트
어떤 블록이 완전히 포함되려면 그 블록 안의 모든 성냥갑이 그날의 토끼 범위에 들어 있어야 한다. 마지막 블록은 K개보다 짧을 수 있으며, 그 안의 모든 성냥갑이 포함되면 완전히 포함된 것으로 처리한다.