hdu3308 LCIS 线段树 难题

线段树_不错的

LCIS

Time Limit: 6000/2000 MS (Java/Others)Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 1607Accepted Submission(s): 715

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⁵).
The next line has n integers(0<=val<=10⁵).
The next m lines each has an operation:
U A B(0<=A,n , 0<=B=10⁵)
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

#include<stdio.h>
struct haha
{
int left;
int right;
int l_len;
int r_len;
int max_len;
}node[100000*4];
int n,a[100000+100];
int mmax(int a,int b)
{
if(a>b) return a;
else return b;
}
int mmin(int a,int b)
{
if(a<b) return a;
else return b;
}
void pushup(int nd)
{
int l_l,r_l;
l_l=node[nd*2].right-node[nd*2].left+1;
r_l=node[nd*2+1].right-node[nd*2+1].left+1;
node[nd].max_len=mmax(node[nd*2].max_len,node[nd*2+1].max_len);
if(a[node[nd*2].right]<a[node[nd*2+1].left])
node[nd].max_len=mmax(node[nd].max_len,node[nd*2].r_len+node[nd*2+1].l_len);
node[nd].l_len=node[nd*2].l_len;
if(node[nd*2].l_len==l_l&&a[node[nd*2].right]<a[node[nd*2+1].left]) node[nd].l_len+=node[nd*2+1].l_len;
node[nd].r_len=node[nd*2+1].r_len;
if(node[nd*2+1].r_len==r_l&&a[node[nd*2].right]<a[node[nd*2+1].left]) node[nd].r_len+=node[nd*2].r_len;
}
void build(int left,int right,int nd)
{
node[nd].left=left;
node[nd].right=right;
if(left==right)
{
node[nd].l_len=node[nd].r_len=node[nd].max_len=1;
return ;
}
int mid=(left+right)/2;
build(left,mid,nd*2);
build(mid+1,right,nd*2+1);
pushup(nd);
}
void update(int pos,int num,int nd)
{
if(node[nd].left==pos&&node[nd].right==pos)
{
a[pos]=num;
return ;
}
int mid=(node[nd].left+node[nd].right)/2;
if(pos<=mid)
update(pos,num,nd*2);
else update(pos,num,nd*2+1);
pushup(nd);
}
int query(int left,int right,int nd)//这个地方最重要了
{
int mid,max;
if(node[nd].left==left&&node[nd].right==right) return node[nd].max_len;
mid=(node[nd].left+node[nd].right)/2;
if(left>mid) return query(left,right,nd*2+1);
else if(right<=mid) return query(left,right,nd*2);
else
{
max=mmax(query(left,mid,nd*2),query(mid+1,right,nd*2+1));//2个分支中较大的
if(a[mid]<a[mid+1]) max=mmax(max,mmin(mid-left+1,node[nd*2].r_len)+mmin(right-mid,node[nd*2+1].l_len));//分支加起来后
/*取2边以及2边合起来后3者中最大的 mmin(mid-left+1,node[nd*2].r_len) 这句话就是为了防止r_len长度超过了当前区段的长度
因为 之前的更新可以看出 求r_len的时候r_len要是接到了另一边就可能长度大于当前区间 这当然是不行的 所以有了那句话*/
return max;
}
}
int main()
{
int i,cas,m,q,b;
char s[2];
while(scanf("%d",&cas)!=EOF)
{
while(cas--)
{
scanf("%d %d",&n,&m);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
build(0,n-1,1);
while(m--)
{
scanf("%s %d %d",s,&q,&b);
if(s[0]=='U')
update(q,b,1);
else printf("%d\n",query(q,b,1));
}
}
}
return 0;
}