HDU 3308 LCIS【線分樹区間連結】

LCIS
http://acm.hdu.edu.cn/showproblem.php?pid=3308
Time Limit: 6000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 9575    Accepted Submission(s): 4165  
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 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

Author
shǎ子
 
Source
HDOJ Monthly Contest – 2010.02.06
 
に言及
n個の数を与えて、2種類の操作があります1種は(U x y)x点の値をyに変えて、もう1種は(Q x y)区間[x,y]の最長連続増分シーケンスの長さを求めます
問題解
sum[i]iが制御する区間における最長厳格増分サブシーケンス長lsum[i]は、iを接頭辞とする最長厳格増分サブシーケンス長rsum[i]は、iを接尾辞とする最長厳格増分サブシーケンス長を表す 
 
[L,R]のiを接頭辞または接尾辞とする最大厳格な増分サブシーケンスの検索は、次の文によって実現される.

min(rsum[rt<<1],m-L+1)+min(lsum[rt<<1|1],R-m)

最初は自分で関数クエリーを書いたが、できないことに気づき、クエリー関数がどこに間違っているのか分からない.上の文しか使えない.

//         l   [L,R]  
//   l     ，   [L,R]                 
int lquery(int L,int R,int l,int r,int rt)
{
	if(l+lsum[rt]-1<=R) return lsum[rt];
	int m=(l+r)>>1;
	if(m>=R) return lquery(L,R,ls);
	int len=lsum[rt<<1];
	if(len=m-l+1&&a[m]=L) return rsum[rt];
int m=(l+r)>>1;
if(m

C++コード

#include
#include

using namespace std;

#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1

const int N=100100;

//sum[i]  i                  
//lsum[i]   i               
//rsum[i]   i                
int sum[N<<2],lsum[N<<2],rsum[N<<2],a[N];

void pushup(int l,int r,int rt)
{
	int m=(l+r)>>1;
	
	sum[rt]=max(sum[rt<<1],sum[rt<<1|1]);
	if(a[m]>1;
build(ls);
build(rs);
pushup(l,r,rt);
}
void update(int L,int C,int l,int r,int rt)
{
if(l==r)
{
a[l]=C;
return;
}
int m=(l+r)>>1;
if(L<=m)
update(L,C,ls);
else
update(L,C,rs);
pushup(l,r,rt);
}
int query(int L,int R,int l,int r,int rt)
{
if(L<=l&&r<=R) return sum[rt];
int m=(l+r)>>1;
if(R<=m) return query(L,R,ls);
if(L>m) return query(L,R,rs);
int len=max(query(L,R,ls),query(L,R,rs));
int tmp;
if(a[m]