로그 분석

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

요약

로그 중간 삽입, 구간 삭제, 위치 구간에 나타나는 서로 다른 이벤트 타입 개수를 묻는 질의를 처리한다.

난이도: 어려움10점 중 8점
유형: 배열, 세그먼트 트리, 이분 탐색, 구현
정답자: 아직 제출이 없습니다

문제

Lisa는 분산 컴퓨터 시스템을 위한 로그 분석 도구를 만들고 있다. 단일 노드의 로그는 뒤에만 덧붙는(append-only) 반면, 분산 로그는 매우 변덕스럽다. 어떤 노드가 온라인이 되면 로그의 과거 위치에 이벤트 묶음을 밀어 넣을 수 있고, 반대로 노드가 오프라인이 되면 일부 로그 항목이 사라질 수 있다.

도구를 안정적이고 빠르게 유지하기 위해, Lisa는 로그의 특정 구간에 나타나는 서로 다른 이벤트 종류의 개수를 추적해야 한다. 분산 처리는 Lisa가 맡고, 여러분은 로컬 엔진을 구현하면 된다.

프로그램은 빈 로그에서 시작하며, 다음 세 가지 연산을 지원해야 한다.

삽입(insert) index number type — 현재 index 위치에 있는 이벤트 바로 앞에 종류가 type인 이벤트를 number개 삽입한다. index 이상의 위치에 있던 모든 이벤트는 오른쪽으로 number칸 밀려 다시 번호가 매겨진다.
삭제(remove) index number — index 위치부터 연속한 이벤트 number개를 지운다.
질의(query) index1 index2 — index1부터 index2까지(양 끝 포함) 위치에 있는 이벤트들 중 서로 다른 종류가 몇 가지인지 센다.

이벤트의 위치 번호는 $1$ 부터 시작한다. 각 이벤트 종류는 하나의 소문자 알파벳으로 표현된다.

입력

첫 줄에는 연산의 개수 $n$ 이 주어진다 ( $1 \le n \le 30000$ ).

이어지는 $n$ 개의 줄에는 각각 하나의 연산이 주어진다. 각 줄은 연산 기호로 시작하며 — 삽입은 +, 삭제는 -, 질의는 ? — 그 뒤에 해당 연산의 인자가 온다.

+ index number type
- index number
? index1 index2

모든 인덱스는 유효하다. 즉 연산이 가리키는 이벤트는 항상 존재하며, 삭제 연산이 로그의 끝을 넘어가는 일은 없다. 삽입과 삭제 연산의 number는 $10000$ 을 넘지 않는다. 이벤트 종류는 소문자 알파벳이다.

출력

각 질의마다 한 줄에 정수 하나를 출력한다 — index1부터 index2까지(양 끝 포함)에 있는 서로 다른 이벤트 종류의 개수.

예제3

예제 1

입력

예상 출력

2
1
3

예제 2
입력
```
4
+ 1 5 a
? 1 5
? 2 4
? 3 3
```
예상 출력
```
1
1
1
```

예제 3

입력

29
+ 1 1 a
+ 2 1 b
+ 3 1 c
+ 4 1 d
+ 5 1 e
+ 6 1 f
+ 7 1 g
+ 8 1 h
+ 9 1 i
+ 10 1 j
+ 11 1 k
+ 12 1 l
+ 13 1 m
+ 14 1 n
+ 15 1 o
+ 16 1 p
+ 17 1 q
+ 18 1 r
+ 19 1 s
+ 20 1 t
+ 21 1 u
+ 22 1 v
+ 23 1 w
+ 24 1 x
+ 25 1 y
+ 26 1 z
? 1 26
? 13 13
? 10 20

예상 출력

26
1
11