시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 70 20 15 27.778%

문제

세계적인 석유 재벌 "규현 조 압둘 티크리티 안드레스 후세인 리오넬 솔레르 살라 마리우 두스 산투스 펠리스 빈 자이드 술탄 친나왓 뱅거 7세"는 집 앞에 정원이 있다. 정원의 관리인은 그냥 홍태석이다. 이 석유 재벌은 앱등이 출신으로, 애플제품이면 모두 사모은다. 그의 집에는 아이팟 터치, 아이팟 나노, 아이폰, 맥북, 애플 티비, 아이패드 등등 전세계의 모든 애플 제품이 있다. 애플을 너무 좋아하기 때문에 정원에는 N개의 사과 나무가 있다.

홍태석은 나무에 비료를 주는 일과, 나무에 대한 통계를 내는 일 2가지만 한다. 다른 일은 해봤자 망치기 때문에, 전혀 하지 않는다.

나무에 비료를 주기 위해서 세계적인 비료 회사 "Telcontar"에서 만든 "BbuRiJaMaJaJaRam"을 사용한다. 이 비료를 나무에 뿌리면, 그 나무는 즉시 1cm 자란다. 이 비료는 병에 담겨져서 나오는데, 모든 병은 제한된 용량 Ci가 있다. 이 Ci는 몇 개의 나무에 비료를 뿌릴지에 쓰인다. 게다가 모든 병에는 나무의 최소 높이 Hi가 있다. 규현 조 압둘 티크리티 안드레스 후세인 리오넬 솔레르 살라 마리우 두스 산투스 펠리스 빈 자이드 술탄 친나왓 뱅거 79세는 가능하면 모든 트리를 크게 만들라고 그냥 홍태석에게 시켰다. 홍태석은 나무 중에 적어도 높이가 Hi 센치미터인 서로 다른 Ci개의 가장 작은 나무를 골라서 비료를 뿌린다.

통계를 낼 때는, 주어진 구간에 속하는 높이의 나무의 개수를 구하는 것이다. 세계적인 석유 재벌 규현 조 압둘 티크리티 안드레스 후세인 리오넬 솔레르 살라 마리우 두스 산투스 펠리스 빈 자이드 술탄 친나왓 뱅거 7세는 홍태석에게 일처리좀 빨리 하라고 강요했기 때문에, 홍태석은 결국 이 일을 대신하는 프로그램을 작성하기로 했다. 홍태석이 해야 하는 일의 목록이 주어졌을 때, 홍태석을 위해 통계를 구해주는 프로그램을 작성하시오.

입력

입력의 첫째 줄에는 N과 M이 있다. N은 나무의 개수이고, M은 홍태석이 해야 하는 일의 개수이다. 둘째 줄에는 각 나무의 처음 높이가 주어진다. 이 높이는 모두 1보다 크거나 같고, N보다 작거나 같은 정수이다. 다음 M개의 줄에는 홍태석이 해야 하는 일이 시간 순서대로 주어진다. 각각의 입력은 문자 Ti (홍태석이 해야 하는 일의 타입)로 시작된다. (Ti = F 또는 Ti = c)

만약, Ti = F라면, 두 개의 정수 Ci와 Hi가 주어진다. 이 줄이 의미하는 것은 홍태석이 높이가 적어도 Hi센치미터인 가장 작은 나무 Ci개를 골라서 "BbuRiJaMaJaJaRam" 비료를 뿌리는 것이다. 만약, 높이가 적어도 Hi센치미터인 나무의 개수가 Ci개 보다 작으면, 남은 비료는 버린다. (한 번 비료를 뿌릴 때면, 하나의 나무에 두번 뿌릴 수 없다.)

만약, Ti = C이면, mini와 maxi가 입력으로 주어진다. 이것은 홍태석이 통계를 내야 하는 개수이다. 나무의 높이 H가 mini와 maxi 사이에 있는 나무의 개수를 구하면 된다. (mini <= H <= maxi) (1<=N,M<=100,000, 1<=Ci<=N, 0<=Hi<=1,000,000,000, 1<=mini<=maxi<=1,000,000,000)

출력

홍태석이 해야 하는 일의 타입이 C일때 마다, 해당하는 나무의 개수를 출력하면 된다.

예제 입력

5 7
1 3 2 5 2
F 2 1
C 3 6
F 2 3
C 6 8
F 2 1
F 2 2
C 3 5

예제 출력

3
0
5

힌트

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2011 1번