P1558 Color Board Game

Abao has started school. Today the teacher brought a very long color board.

The color board has length $L$, where $L$ is a positive integer, so we can evenly divide it into $L$ small squares, each $1$ centimeter long, labeled from left to right as $1, 2, \dots, L$. Currently the board has only one color. The teacher tells Abao that only two operations are allowed on the board: 1. `C A B C` means to paint all squares numbered from $A$ to $B$ with color $C$. 2. `P A B` means a query: how many different colors appear among squares numbered from $A$ to $B$. There are $T$ types of paint in the school’s paint box. For simplicity, we label them as $1, 2, \dots, T$. Initially, the entire board has color $1$. Facing such a complex problem, Abao asks for your help. Can you help him?

The first line contains $3$ integers $L$ $(1 \le L \le 10^5)$, $T$ $(1 \le T \le 30)$, and $O$ $(1 \le O \le 10^5)$. Here $O$ is the number of operations. Then follow $O$ lines, each describing an operation in the form `C A B C` or `P A B` (here $A, B, C$ are integers; it is possible that $A > B$, in which case you should swap $A$ and $B$).

For each query from the teacher, output the corresponding answer. Print one integer per line.

Constraints $1 \le L \le 10^5$, $1 \le T \le 30$, $1 \le O \le 10^5$. $1 \le A, B \le L$ (not guaranteed that $A \le B$), $1 \le C \le T$. Translated by ChatGPT 5