# 描述

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.

## Input

The input contains many lines.

Each line contains a operation. It may be 0, 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 3.

$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$.

## Output

For each operation $2$, output an integer means the answer.

# 思路

• 菜鸡表示看到这题的第一反应就是线段树，可是用线段树维护什么呢？由于我们要查询一个区间内有多少种颜色，我们可以考虑沿着$y$方向建线段树，维护某种颜色$x$最小值，只要最小值在我们查询的$x$内，就有这种颜色。是的，你没看错，每一种颜色开一个线段树，最多也就$50$个。
• 嗯，直接建$50$个线段树显然肉眼可见慢+MLE，所以我们要动态建树，因为单点更新每次操作只会多出$\log n$个新结点，这样的空间复杂度就是$q\log n$。然后单点更新和区间查询都是正常思路。

0%