[Login|Register]
Problems

Status

Rank

Problem 1270
序列操作
Time Limit: 2000ms
Memory Limit: 65536kb
Description
给你一个由N个正整数组成的序列,现在你可以对该序列进行如下两种操作:
Q L R:输出区间[L,R](1<=L,R<=N)中最长连续不下降子序列的长度。
C L R P:将区间[L,R] (1<=L,R<=N)中的每个整数都改变成整数P。
作为USTC的程序精英们,你能很顺利的解决这个问题么?
Input
第一行输入一个正整数T,代表下面有T组测试数据(T<=10)。
针对每组测试数据:
首先输入两个正整数N Q(1<=N<=100000,1<=Q<=100000),分别代表序列的长度和操作的次数。
接着输入N个正整数(每个正整数不大于1000)。
最后输入Q行,代表有Q次操作,每行有两种可能的形式:Q L R 或
C L R P。意义如上所示,其中P不大于1000。
注意: 1<=L,R<=N, L有可能会大于R;下标从1开始。
Output
针对每次Q L R操作,输出对应区间[L,R]中最长连续不下降子序列的长度。
Sample Input
1
6 5
1 2 3 4 5 6 
Q 1 6         
C 4 3 2
Q 1 3
C 4 5 3
Q 2 5
Sample Output
6
3
4
University of Science and Technology of China
Online Judge for ACM/ICPC
Processed in 1.4ms with 1 query(s).