Background

Every day I keep thinking about dying.

Maybe I should just die.

Magical Girl Site? What is that?

“How unfortunate, how unfortunate.”

“To someone like you—”

“I shall grant you the power of magic.”

Amagai Kosame

Sigh, introductions are such a hassle.

You collapsed from overusing the wand, and after that you kept losing consciousness.

So I healed you.

At 19:23 on August 11 in the future,

on that day, the tempest will arrive—

The tempest will bring an end to this rotten world and open the gate to a new world. But during this process, most humans will probably die.

The arrival of the tempest is unavoidable, but there is only one way to obtain salvation—

That is to fill the King’s stomach.

The King feeds on humans’ negative energy. As long as you offer this energy, you can avoid the death brought by the tempest.

By using the wands given by the Magical Girl Site, you can store negative energy into the wand.

Only by using the wand as much as possible, and offering more negative energy than other magical girls, can you become someone the tempest will pardon.

If you want to live, then on the day of the tempest, hand the wand filled with negative energy to our Magical Girl Site.

In the end, we wish you a wonderful end.

Remove all negative emotions from humans.

The tempest will surely sweep across the world.

Problem Description

Amagai Kosame gives you a sequence of length $n$. Define the sub-intervals of an interval $[l,r]$ as all intervals of the form $[l',r']$, where $l',r'$ are integers and $l \le l' \le r' \le r$.

There are $m$ operations:

1 x y: Modify the value at position $x$ to $y$.

2 l r x: Query how many sub-intervals in $[l,r]$ have maximum value less than or equal to $x$.

Input Format

The first line contains two integers $n,m$. The second line contains $n$ integers representing the sequence.

Then follow $m$ lines, each in the form 1 x y or 2 l r x, describing each operation.

Output Format

For each operation of type 2, output one line with one number, representing the answer.

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

1
1
7
0

Hint

Idea: nzhtl1477, Solution: nzhtl1477, Code: ccz181078, Data: ccz181078

For $100\%$ of the testdata, $n,m \le 3 \times 10^5$, $1 \le l \le r \le n$, $1 \le x, y \le n$, each element in the sequence is in $[1,n]$, and all numbers are integers.

Translated by ChatGPT 5