Problem C - USTC Online Judge

Rank

Problem C

序列操作

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

[Submit|Discuss|Add to bookmark]