P2464 [SDOI2008] Depressed Little J

Little J is a librarian at the National Library, and his job is to manage a huge bookshelf. Although he is diligent, the bookshelf is so large that his efficiency is always low, putting him at risk of being fired, which makes him depressed. Specifically, the bookshelf consists of $N$ positions, numbered from $1$ to $N$. Each position holds one book, and each book has a specific code. Little J’s job has two types: 1. The library frequently purchases new books, and the shelf is always full at any time, so a book at some position has to be removed and replaced with the newly purchased one. 2. Little J needs to answer customer queries. A customer will ask how many books with a given code appear in a certain contiguous segment of positions. For example, there are $5$ positions, and initially the codes of the books on the positions are $1, 2, 3, 4, 5$. A customer asks how many books with code "2" are in positions $1$ to $3$. The answer is $1$. A customer asks how many books with code "1" are in positions $1$ to $3$. The answer is $1$. At this point, the library purchases a book with code "1" and puts it at position $2$. A customer asks how many books with code "2" are in positions $1$ to $3$. The answer is $0$. A customer asks how many books with code "1" are in positions $1$ to $3$. The answer is $2$. ... Your task is to write a program to answer each customer’s query.

The first line contains two integers $N, M$, meaning there are $N$ positions and $M$ operations. The next line contains $N$ integers $A_1, A_2, \ldots , A_N$, where $A_i$ is the code of the book initially at position $i$. The next $M$ lines each represent an operation, and each line begins with a character. If the character is `C`, it means the library purchases a new book, followed by two integers $A, P$ ($1 \le A \le N$), meaning the book is placed at position $A$, and its code is $P$. If the character is `Q`, it represents a customer query, followed by three integers $A, B, K$ ($1 \le A \le B \le N$), meaning to query how many books with code $K$ appear from position $A$ to position $B$ (inclusive).

For each customer query, output one integer representing the result of the query.

For $40\%$ of the testdata, $1 \le N, M \le 5000$. For $100\%$ of the testdata, $1 \le N, M \le {10}^5$. For $100\%$ of the testdata, all book codes that appear are positive integers not greater than $2^{31} - 1$. Translated by ChatGPT 5