2358: Imagine
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：1
解决：1
题目描述
In some imaginary city made up especially for this problem, there are two fictional political parties
that were named A and B (because these names are conveniently short and also nobody really
cared).
In the centre of this non-existent city you are supposed to imagine a large billboard of 10.24
metres in width and 10.24 metres in height, essentially a 1024 × 1024 grid of square centimetres.
Every now and then a political activist comes around and puts a 1cm × 1cm sticker with either
an A or a B, depending on his or her assumed political orientation, on the grid. Any sticker that
was put on that particular position before, no matter from which of the parties, becomes invisible.
This might all sound a wee bit unrealistic, but you need to keep in mind that it is in fact not real.
It is just for the problem.
Now, for some obscure reason, that could have been totally justified had someone put a bit more
effort into writing this assignment, a list is maintained with the exact location and denomination
of every single sticker that was put up, in chronological order.
At any moment one might wonder how many A’s and B’s there currently are within some
subrectangle of the grid. Such question may come up, for example, when someone looks at
the billboard from a large distance, with a rectangular telescope. You will find such queries in
the input, mixed with the information about when what kind of sticker was put where, all in
chronological order. Can you write a program that can handle such queries quickly?
You may assume that the grid has been initialized like a checker board with an A in the top
left corner at x = y = 1, hence in the following way:
A B A B A B A B A
B A B A B A B A B
A B A B A B A B A
B A B A B A B A B
输入
The input consists of a single test case, which has the following format:
• One line with an integer N , satisfying 1 ≤ N ≤ 1, 000, 000: the total number of stickers and
queries in the input.
• N lines, each of which is formatted as one of two alternatives:
– A line starting with the character ’A’or ’B’followed by two integers x and y, satisfying
1 ≤ x,y ≤ 1024, denoting a sticker which is put on the grid.
– A line with the character ’R’ followed by four integers x1 , y1 , x2 and y 2 , satisfying
1 ≤ x1 ≤ x2 ≤ 1024 and 1 ≤ y1 ≤ y2 ≤ 1024, denoting the top left and bottom right
coordinates of a queried subrectangle.
Alphabetic characters and integers on the same line are separated by single spaces. You can make
no assumptions about the way the stickers and queries are interleaved in the input.
输出
For every query in the input, the output should contain two numbers, on a single line: the numbers
of A’s and B’s in the queried subrectangle at the moment of the query, separated by a single space.
样例输入 复制
7
R 1 1 3 3
A 2 3
A 1 3
R 1 1 3 3
B 2 2
B 3 3
R 2 2 3 3样例输出 复制
5 4
6 3
1 3