퀘스트 중인 모험가

시간 제한3초메모리 제한256 MB

요약
완료한 퀘스트 번호 집합을 갱신하면서 [L, R] 범위에서 아직 완료하지 않은 정수의 개수를 구하는 문제입니다.
난이도

보통10점 중 6점

유형
해시맵, 정렬, 이분 탐색, 구현
정답자
아직 제출이 없습니다

문제

모험가는 온라인 RPG 월드 아트 위그드라실(WAY)에서 활동하는 랭커이며, 매일 퀘스트 달성을 즐긴다.

WAY에는 −1,000,000,000-1{,}000{,}000{,}000부터 1,000,000,0001{,}000{,}000{,}000까지의 모든 정수 번호마다 퀘스트가 하나씩 있다. 특정 범위의 퀘스트를 모두 달성하면 업적을 받을 수 있다.

퀘스트를 항상 순서대로 달성할 수 있는 것은 아니라서, 업적마다 남은 퀘스트 수를 매번 계산해야 한다. 애드온은 달성 기록을 반영하고, 주어진 범위에서 아직 달성하지 못한 퀘스트의 개수를 알려준다.

달성 기록과 요청이 주어졌을 때, 각 조회 요청에 답하는 프로그램을 작성하라.

입력

첫째 줄에 지금까지 달성한 퀘스트의 개수 NN이 주어진다. (1≤N≤1,000,000)(1 \le N \le 1{,}000{,}000)

둘째 줄에 달성한 퀘스트 번호 NN개 Q1,…,QNQ_1, \dots, Q_N이 주어진다. (−1,000,000,000≤Qi≤1,000,000,000,Qi<Qi+1)(-1{,}000{,}000{,}000 \le Q_i \le 1{,}000{,}000{,}000, Q_i < Q_{i+1})

셋째 줄에 요청의 개수 MM이 주어진다. (1≤M≤1,000,000)(1 \le M \le 1{,}000{,}000)

이어지는 MM개의 줄에는 요청이 하나씩 주어진다.

  • 1 X1\ X: 번호가 XX인 퀘스트를 달성했다. 이를 기록에 반영한다. (−1,000,000,000≤X≤1,000,000,000)(-1{,}000{,}000{,}000 \le X \le 1{,}000{,}000{,}000)
  • 2 L R2\ L\ R: 번호가 LL 이상 RR 이하인 퀘스트 중 아직 달성하지 못한 퀘스트의 개수를 출력한다. (−1,000,000,000≤L≤R≤1,000,000,000)(-1{,}000{,}000{,}000 \le L \le R \le 1{,}000{,}000{,}000)

출력

종류가 22인 요청마다, 조건을 만족하는 미달성 퀘스트의 개수를 한 줄에 하나씩 출력한다.

예제1

  1. 예제 1

    입력
    3
1 10 20
4
2 1 20
1 5
2 1 20
2 1 1
    예상 출력
    17
16
0