All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
You are given a Cartesian plane, and you are asked to support the following three kinds of operations:
- I x1 y1 x2 y2: add an axes-parallel rectangle on the plane. The bottom-left corner has coordinates (x1, y1), the top-right one has coordinates (x2, y2)
- D index: remove the retangle that was added during the index-th addition operation
- Q x1 y1 x2 y2: output the number of rectangles on the plane that have the common area with the rectangle with a bottom-left corner coordinates (x1, y1) and a top-right corner coordinates (x2, y2).
Please notice that, even if the two rectangles only share a common point, they are still regarded as sharing common area
Also, there can be a few same rectangles on the plane, they should be regarded as a few different rectangles.
There are Q operations in all, can you fulfill them?
The first line contains an integer Q.
The next Q lines represent the operations you are to deal with. Each of them contains an operation in one of the three forms above.
For each Q-type operation, output the result on the separate line of the output.
- 1 <= Q <= 100000
- 1 <= x1 <= x2 <= 109
- 1 <= y1 <= y2 <= 109
I 1 1 2 2
I 2 2 3 3
Q 3 3 4 4
Q 3 3 4 4
In the third operation, the rectangle (2, 2)-(3, 3) has a common point with the given rectangle. But in the fifth operation, as the rectangle (2, 2)-(3, 3) has been removed, so there are no rectangles that has the common area with the given rectangle.
|Tags||fenwick, hard, sept14, sqrt-decomp, xiaodao|
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.