瑶瑶想要玩滑梯

Time Limit: 2000/1000MS (Java/Others) Memory Limit: 512000/256000KB (Java/Others)

Problem Description

众所周知,瑶瑶(tsyao)是个贪玩的萌妹子,特别喜欢闹腾,恰好今天是一个风和日丽的日子,瑶瑶嚷着让姐姐带她去去公园玩滑梯,可是公园的滑梯比较独特,由单位积木搭成,积木是排成一排搭好,每列有xi个积木,共n列。小明能够对积木进行m次操作:

1.U L R yi         : 将[L,R]列的积木高度全都改为yi

2.Q L R           : 查询[L,R]列最长连续上升的列长度(LCIS)

知道[L,R]列最长连续上升的列长度过后,瑶瑶就可以开开心心地玩滑梯啦!

Ps:连续上升的列长度指对于一段合法区间,都有

       话说积木是平的,瑶瑶是怎么从高处滑到低处的呢??作为姐姐也不知道,很想知道吧?你去问她吧。。

Input

第一行 两个整数n,m;

第二行 n个整数,分别为[1,n]区间每列积木个数;

接下来m行为m个操作

Output

输出x行,每行为每次操作2的查询结果。

Sample Input

5 4
2 1 2 3 1
Q 1 4
Q 2 5
U 2 4 3
Q 1 5

Sample Output

3
3
2

Hint

对于 100%的数据,有1 ≤ n ≤ 10^5 , 1 ≤ m ≤ 10^5 , 1 ≤ xi ≤ 10^8。

单组输入,共10组数据。

Source

tsyao

Manager

Information
Solved Number92
Submit Number309
Problem Tags
data structures
No tag edit access
温馨提示:AC后可以编辑标签哦. ^-^
Login
LoginCancel