博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
hdu 3308 LCIS
阅读量:5789 次
发布时间:2019-06-18

本文共 1667 字,大约阅读时间需要 5 分钟。

LCIS

Time Limit: 6000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 2640    Accepted Submission(s): 1143

Problem Description
Given n integers.
You have two operations:
U A B: replace the Ath number by B. (index counting from 0)
Q A B: output the length of the longest consecutive increasing subsequence (LCIS) in [a, b].
 
Input
T in the first line, indicating the case number.
Each case starts with two integers n , m(0<n,m<=10
5).
The next line has n integers(0<=val<=10
5).
The next m lines each has an operation:
U A B(0<=A,n , 0<=B=10
5)
OR
Q A B(0<=A<=B< n).
 
Output
For each Q, output the answer.
 
Sample Input
1
10 10
7 7 3 3 5 9 9 8 1 8
Q 6 6
U 3 4
Q 0 1
Q 0 5
Q 4 7
Q 3 5
Q 0 2
Q 4 6
U 6 10
Q 0 9
Sample Output
1
1
4
2
3
1
2
5
1 /**  2 这是一道经典的线段树题目。  3 有分治的思想在里面  4 求解区间[L , R]最长递增子序列的长度。  5   6 对于一个线段树的区间  7 我们需要保存左端点的值,右端点的值,  8 以及分别包含左右端点所能达到的最长递增子序列的长度  9 lmaxn ,rmaxn;还要有一个保存区间最彻底子序列的值maxn。 10  11 **/ 12 #include
13 #include
14 #include
15 #include
16 using namespace std; 17 18 struct node 19 { 20 int l,r,len; 21 int lnum,rnum,lmaxn,rmaxn,maxn; 22 }f[100002*4]; 23 int date; 24 25 /** 26 向上更新函数。 27 **/ 28 void up(int n,int LChild,int RChild) 29 { 30 f[n].lnum = f[LChild].lnum; 31 f[n].rnum = f[RChild].rnum; 32 33 f[n].lmaxn = (f[LChild].lmaxn==f[LChild].len && f[LChild].rnum
=wz) update(wz,num,n*2); 76 else if(mid
=r) return query(l,r,n*2); 88 else if(mid

 

 

 

 

转载于:https://www.cnblogs.com/tom987690183/archive/2013/05/02/3055258.html

你可能感兴趣的文章
vsftpd 自动安装脚本
查看>>
mybatis 3.3 源码阅读(一)
查看>>
tr以及管道经典练习题以及详细过程
查看>>
Linux新手训练营--基础篇
查看>>
Tigase输出从客户端和服务器的请求应答日志
查看>>
shell学习笔记
查看>>
liunx基础命令
查看>>
python异常处理
查看>>
mysqlbinlog
查看>>
UIScrollView、UIPageControl总结
查看>>
MessagePack踩坑之一
查看>>
未来DDOS防护市场的发展趋势是什么?
查看>>
代码面试需要知道的8种数据结构(附面试题及答案链接)
查看>>
redmine 整合版本库
查看>>
0016-Avro序列化&反序列化和Spark读取Avro数据
查看>>
php打印二维数组问题
查看>>
面向切面编程(AOP)的理解
查看>>
如何成为一名Java初级程序员
查看>>
API接口实现短信自动发送,短信验证码接口示例
查看>>
WordPress 映射
查看>>