Do you like painting? Little D doesn’t like painting, especially messy color paintings. Now Little B is painting. To prevent him from drawing messy painting, Little D asks you to write a program to maintain following operations. The specific format of these operations is as follows.
$0$ : clear all the points.
$1\ x\ y\ c$ : add a point which color is $c$ at point $(x,y)$.
$2\ x\ y_1\ y_2$ : count how many different colors in the square $(1,y_1)$ and $(x,y_2)$. That is to say, if there is a point $(a,b)$ colored $c$, that $1≤a≤x$ and $y_1≤b≤y_2$, then the color $c$ should be counted.
$3$ : exit.
The input contains many lines.
Each line contains a operation. It may be
1 x y c $( 1≤x,y≤10 ^ 6,0≤c≤50 )$,
2 x y1 y2 $(1≤x,y_1,y_2≤10 ^ 6 )$ or
$x,y,c,y_1,y_2$ are all integers.
Assume the last operation is $3$ and it appears only once.
There are at most $150000$ continuous operations of operation $1$ and operation $2$.
There are at most $10$ operation $0$.
For each operation $2$, output an integer means the answer.
- 嗯，直接建$50$个线段树显然肉眼可见慢+MLE，所以我们要动态建树，因为单点更新每次操作只会多出$\log n$个新结点，这样的空间复杂度就是$q\log n$。然后单点更新和区间查询都是正常思路。