CRAYON - Crayon
Mary love painting so much, but as we know she can't draw very well. There is no one appreciate her works, so she come up with a puzzle with herself....
There are only one case in each input file, the first line is a integer N (N <= 1,000,00) denoted the total operations executed by Mary. Then following N lines, each line is one of the folling operations.
- D L R: draw a segment [L, R], 1 <= L <= R <= 1,000,000,000
- C I: clear the ith added segment. It’s guaranteed that the every added segment will be cleared only once.
- Q L R: query the number of segment sharing at least a common point with interval [L, R]. 1 <= L <= R <= 1,000,000,000.
( then following n operations ... )
(for each query, print the result on a single line ... )
Input: 6 D 1 3 D 2 4 Q 2 3 D 2 4 C 2 Q 2 3 Output: 2 2
Clear index is 1-based. Clear operations do not affect the indexes.
Sorry for Inconvenience ... but Mary is a character in a small RPG game called Ib ...
[Reminder] This is NOT my problem.