Background

...Feathers.

Feathers falling from the sky.

Pure white, like snow,

swaying in the sea breeze,

dancing in the cool wind,

as if trying to carry away someone's heart—divine feathers.

...

"Please."

Who said that?

"Please."

"Save us."

...A dream.

I know this is a dream.

Then, that person spoke again, in my pure white dream:

"We will always be waiting here..."

So, I set off on a long journey.

There is a place I must go.

To fulfill that person's wish.

So I think, if...

if my wish could come true,

then maybe, you and I...

...The world has ended.

It has already ended.

I was too late—no matter what, everything...

...Hateful.

Unforgivable.

I...

...I will absolutely never forgive you.

Now, set out...

I will... I will definitely... take you...!

Hand... hand in hand, and hearts can be connected.

...My left hand is not holding anyone. It is my hand.

Grant the wish.

Only this fact will remain, and then the two of us will part.

It was in hope of this that the two of us walked together until today.

Is that so?

Come, let's set out, to choose that one-and-only tomorrow.

Problem Description

Erjiedang Zhenhong gives you a sequence $a$ of length $n$, with $m$ operations.

1. For every number greater than $x$ in the interval $[l,r]$, subtract $x$ from it.
2. Query the number of occurrences of $x$ in the interval $[l,r]$.

Input Format

The first line contains two integers $n$ and $m$.

The second line contains $n$ integers representing the sequence $a$.

Then follow $m$ lines, each containing four integers:

• 1 l r x: For all numbers greater than $x$ in $[l,r]$, subtract $x$.
• 2 l r x: Query the number of occurrences of $x$ in $[l,r]`.

Output Format

For each type-2 query, output one integer representing the answer.

5 6
1 5 5 5 8
2 2 5 5
1 2 4 3
2 2 5 2
2 2 5 5
1 3 5 1
2 1 5 1

3
3
0
3

Hint

Idea: nzhtl1477, Solution: nzhtl1477, Code: nzhtl1477, Data: nzhtl1477.

For $100\%$ of the testdata, $1 \le n \le 10^6$, $1 \le m \le 5 \times 10^5$, $1 \le l \le r \le n$, $0 \le a_i, x \le 10^5 + 1$.

By nzhtl1477.

Translated by ChatGPT 5