Marslaste õunaaed

시간 제한2초메모리 제한1024 MB

요약

배열에서 값이 X인 원소를 모두 X+1로 늘리는 갱신과, 구간 [L,R]에서 값이 Y 이하인 원소의 개수를 세는 질의를 처리한다.

난이도: 어려움10점 중 8점
유형: 세그먼트 트리, 이분 탐색, 누적 합, 구현
정답자: 아직 제출이 없습니다

문제

Zaqquat peab Marsil õunaaeda, kus kasvab $N$ õunapuud. Puud on pikas sirges reas ja nummerdatud $1 \ldots N$ .

Marsi õunad küpsevad järgmiste reeglite kohaselt:

Aasta alguses on puu number $i$ õunte küpsus $Z\_i$ .
Mingitel hetkedel aasta jooksul küpsevad kõik õunad küpsusega $X$ ühe astme võrra, saades uueks küpsuseks $X + 1$ .

Aeg-ajalt tahab Zaqquat teada, kui palju on õunapuude $L$ kuni $R$ hulgas selliseid, mille õunte küpsus ei ületa $Y$ .

Kirjutada programm, mis modelleerib õunte küpsemist ja vastab Zaqquati päringutele.

입력

Faili esimesel real on õunapuude arv $N$ ( $1 \le N \le 500\\,000$ ) ja sündmuste arv $Q$ ( $1 \le Q \le 500\\,000$ ).

Faili teisel real on $N$ tühikutega eraldatud täisarvu $Z\_i$ ( $1 \le Z\_i \le 1\\,000\\,000$ ): õunte küpsused aasta algul.

Järgmisel $Q$ real on igaühel ühe sündmuse kirjeldus. Rea alguses on sündmuse tüüp $T$ :

Kui $T = 1$ , on real lisaks veel täisarv $X$ ( $1 \le X \le 1\\,500\\,000$ ), mis näitab, et õunad küpsusega $X$ saavad uueks küpsuseks $X + 1$ .
Kui $T = 2$ , on real lisaks veel kolm täisarvu $L$ , $R$ ja $Y$ ( $1 \le L \le R \le N$ , $1 \le Y \le 1\\,500\\,000$ ), mis näitavad, et Zaqquat tahab teada, kui palju on õunapuude $L$ kuni $R$ (mõlemad kaasa arvatud) hulgas selliseid, millel olevate õunte küpsus on maksimaalselt $Y$ .

Sündmused on failis nende toimumise kronoloogilises järjekorras.

출력

Faili väljastada iga teist tüüpi sündmuse kohta vastus Zaqquati küsimusele. Vastused väljastada igaüks eraldi reale küsimuste kronoloogilises järjekorras.

예제1

예제 1

입력

7 9
4 1 2 1 4 4 7
2 1 4 1
1 1
2 1 3 1
1 1
1 2
2 3 5 3
2 3 5 2
1 4
2 2 6 4

예상 출력