D. LCIS time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output This problem differs from one which was on the online contest.

给定N个数，两种操作 U  A B：把第A个数变为B（从0开始计数） Q A B ：查询A到B内，最长的连续上升序列长度 向上更新部分要注意细节 对于左连续的话，可以由左孩子的左连续得来，但是可能包括右孩子的左连续，要进行判断左孩子的左连续是否是整个区间，而且中间的结合是否满足递增 右连续一样。 对于整个区间的最值，可能来源与左右孩子的最值，也可以来源于两个区间的中间部分。 更新

这道题是CD老OJ上面的一道题，现在在新OJ上的题号是360，开始在VJ上做的提交一直RE（囧）。后来才知道OJ移位了。 这道题是一个简单的成段更新+区间合并的线段树的题，1A还让我小激动了一下 这道题的大概意思是有两种操作，一种是成段地增加一个值，另外一种是询问从l到r这段区间内的最长递增子序列 首先先分析一下，如果某一段的值成段地增加一个量，那么该区间内的数的相对大小是不变的，因此递增子

http://acm.hdu.edu.cn/showproblem.php?pid=4718 链上LCIS 用区间合并解决 线段树每次查询都带回该区间内的左值 右值 左连续段 右连续段 最大连续段 然后和该链上的上一次查询合并 这里直接当做线段树区间合并的法子写的 uv两点顺着两条链向上爬 会师后特殊处理即可 7000+的代码 debug一天。。 爬链时开了很多没用的变量 反正多了没错。。

题目 求两个序列的最长公共上升子序列 分析 首先，优化的方法 for (int i=1;i<=n;i++)for (int j=1;j<=n;j++)if (a[i]==b[j])for (int k=0;k<j;k++)if (b[k]<a[i])f[i][j]=max(f[i][j],f[i-1][k]+1); 但是 O ( n 3 ) O(n^3) O(n3)的算法对于 n

线段树 跟上次做的0 1 反转基本相同 http://acm.uestc.edu.cn/problem.php?pid=1425 注意：sample输出是没输出case数，害我wa了好多次。。。 #include<iostream>#include<cstdio>#include<cstring>using namespace std;#define ls (rt<<1)#def