首页 > 代码库 > HDOJ 题目3308 LCIS(线段树,区间查询,区间合并)

HDOJ 题目3308 LCIS(线段树,区间查询,区间合并)

LCIS

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


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

Recommend
wxl   |   We have carefully selected several similar problems for you:  3397 1542 1828 2871 1255 

ac代码
#include<stdio.h>
#include<string.h>
#define max(a,b) (a>b?

a:b) #define min(a,b) (a>b?

b:a) struct s { int lnum,rnum; int lmax,rmax,mmax; }node[1000100<<2]; void init(int tr,int num) { node[tr].lnum=num; node[tr].rnum=num; node[tr].lmax=1; node[tr].rmax=1; node[tr].mmax=1; } void pushup(int tr,int m) { node[tr].lnum=node[tr<<1].lnum; node[tr].rnum=node[tr<<1|1].rnum; node[tr].lmax=node[tr<<1].lmax; node[tr].rmax=node[tr<<1|1].rmax; node[tr].mmax=max(node[tr<<1].mmax,node[tr<<1|1].mmax); if(node[tr<<1].rnum<node[tr<<1|1].lnum) { node[tr].mmax=max(node[tr].mmax,node[tr<<1].rmax+node[tr<<1|1].lmax); if(node[tr<<1].lmax==m-(m>>1)) node[tr].lmax+=node[tr<<1|1].lmax; if(node[tr<<1|1].rmax==(m>>1)) node[tr].rmax+=node[tr<<1].rmax; } } void build(int l,int r,int tr) { if(l==r) { int num; scanf("%d",&num); init(tr,num); return; } int mid=(l+r)>>1; build(l,mid,tr<<1); build(mid+1,r,tr<<1|1); pushup(tr,r-l+1); } void update(int pos,int num,int l,int r,int tr) { if(l==r) { init(tr,num); return; } int mid=(l+r)>>1; if(pos<=mid) { update(pos,num,l,mid,tr<<1); } else update(pos,num,mid+1,r,tr<<1|1); pushup(tr,r-l+1); } int query(int L,int R,int l,int r,int tr) { if(L<=l&&R>=r) { return node[tr].mmax; } int mid=(l+r)>>1; int temp1=0,temp2=0,temp3=0; if(L<=mid) temp1=query(L,R,l,mid,tr<<1); if(R>mid) temp2=query(L,R,mid+1,r,tr<<1|1); if(L<=mid&&R>mid&&node[tr<<1].rnum<node[tr<<1|1].lnum) temp3=min(mid-L+1,node[tr<<1].rmax)+min(R-mid,node[tr<<1|1].lmax); int ans=max(temp1,max(temp2,temp3)); return ans; } int main() { int t; scanf("%d",&t); while(t--) { int n,m; scanf("%d%d",&n,&m); build(1,n,1); while(m--) { char s[2]; int a,b; scanf("%s%d%d",s,&a,&b); if(s[0]==‘U‘) { update(a+1,b,1,n,1); } else { printf("%d\n",query(a+1,b+1,1,n,1)); } } } }



HDOJ 题目3308 LCIS(线段树,区间查询,区间合并)