瑶瑶想要玩滑梯
Time Limit:10000/5000 MS (Java/Others)
Memory Limit:512000/256000 KB (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
tsyao
传送门：ACDream 1101 瑶瑶想要玩滑梯
题目大意：给你一个区间，每次修改可以修改一段区间的值，每次查询一个区间问这个区间上的最长连续上升的列长度(LCIS)是多长（严格上升）。
题目分析：这题可以用线段树求解，模型是区间替换和区间合并，只要维护每个区间的左右端点即可。
传送门：ACDream 1101 瑶瑶想要玩滑梯
题目大意：给你一个区间，每次修改可以修改一段区间的值，每次查询一个区间问这个区间上的最长连续上升的列长度(LCIS)是多长（严格上升）。
题目分析：这题可以用线段树求解，模型是区间替换和区间合并，只要维护每个区间的左右端点即可。
代码如下：
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std ;
#define lson l , m , o << 1
#define rson m + 1 , r , o << 1 | 1
const int maxT = 1000000;
const int maxN = 100005;
int a[ maxN ] ;
int maxo[ maxT ] , maxl[ maxT ] , maxr[ maxT ] ;
int numl[ maxT ] , numr[ maxT ] , mark[ maxT ] ;
int max ( const int X , const int Y ) {
return X > Y ? X : Y ;
}
int min ( const int X , const int Y ) {
return X < Y ? X : Y ;
}
void PushUp ( int l , int r , int o ) {
int m = ( l + r ) >> 1 ;
maxo[ o ] = max ( maxo[ o << 1 ] , maxo[ o << 1 | 1 ] ) ;
maxl[ o ] = maxl[ o << 1 ] ;
maxr[ o ] = maxr[ o << 1 | 1 ] ;
numl[ o ] = numl[ o << 1 ] ;
numr[ o ] = numr[ o << 1 | 1 ] ;
if ( numr[ o << 1 ] < numl[ o << 1 | 1 ] ) {
maxo[ o ] = max ( maxo[ o ] , maxr[ o << 1 ] + maxl[ o << 1 | 1 ] ) ;
if ( maxl[ o ] == m - l + 1 ) {
maxl[ o ] += maxl[ o << 1 | 1 ] ;
}
if ( maxr[ o ] == r - m ) {
maxr[ o ] += maxr[ o << 1 ] ;
}
}
}
void PushDown ( int o ) {
if ( mark[ o ] ) {
mark[ o << 1 ] = mark[ o << 1 | 1 ] = mark[ o ] ;
numl[ o << 1 ] = numr[ o << 1 ] = mark[ o << 1 ] ;
maxl[ o << 1 ] = maxr[ o << 1 ] = maxo[ o << 1 ] = 1 ;
numl[ o << 1 | 1 ] = numr[ o << 1 | 1 ] = mark[ o << 1 | 1 ] ;
maxl[ o << 1 | 1 ] = maxr[ o << 1 | 1 ] = maxo[ o << 1 | 1 ] = 1 ;
mark[ o ] = 0 ;
}
}
void Build ( int l , int r , int o ) {
mark[ o ] = 0 ;
if ( l == r ) {
maxo[ o ] = maxl[ o ] = maxr[ o ] = 1 ;
numl[ o ] = numr[ o ] = a[ l ] ;
}
else {
int m = ( l + r ) >> 1 ;
Build ( lson ) ;
Build ( rson ) ;
PushUp ( l , r , o ) ;
}
}
void Update ( int L , int R , int c , int l , int r , int o ) {
if ( L <= l && r <= R ) {
maxo[ o ] = maxl[ o ] = maxr[ o ] = 1 ;
numl[ o ] = numr[ o ] = mark[ o ] = c ;
return ;
}
PushDown ( o ) ;
int m = ( l + r ) >> 1 ;
if ( L <= m ) Update ( L , R , c , lson ) ;
if ( m < R ) Update ( L , R , c , rson ) ;
PushUp ( l , r , o ) ;
}
int Query ( int L , int R , int l , int r , int o ) {
if ( L <= l && r <= R ) return maxo[ o ] ;
PushDown ( o ) ;
int tmp1 = 0 , tmp2 = 0 , tmp3 = 0 , m = ( l + r ) >> 1 ;
if ( L <= m ) tmp1 = Query ( L , R , lson ) ;
if ( m < R ) tmp2 = Query ( L , R , rson ) ;
if ( L <= m && m < R ) {
if ( numr[ o << 1 ] < numl[ o << 1 | 1 ] ) {
tmp3 = min ( maxr[ o << 1 ] , m - L + 1 ) + min ( maxl[ o << 1 | 1 ] , R - m ) ;
}
}
return max ( tmp1 , max ( tmp2 , tmp3 ) ) ;
}
void work () {
int n , m , L , R , C;
char ch[ 5 ] ;
scanf ( "%d%d" , &n , &m ) ;
for ( int i = 1 ; i <= n ; ++ i ) {
scanf ( "%d", &a[i] ) ;
}
Build ( 1 , n , 1 ) ;
for ( int i = 0 ; i < m ; ++ i ) {
scanf ( "%s" , ch ) ;
if ( ch[ 0 ] == 'U' ) {
scanf ( "%d%d%d" , &L , &R , &C ) ;
Update ( L , R , C , 1 , n , 1 ) ;
}
else {
scanf ( "%d%d" , &L , &R ) ;
int ans = Query ( L , R , 1 , n , 1 ) ;
printf ( "%d\n" , ans ) ;
}
}
}
int main () {
work () ;
return 0 ;
}