首页 > 代码库 > 线段树 [HDU 3308] LCIS
线段树 [HDU 3308] LCIS
LCIS
Time Limit: 6000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 4437 Accepted Submission(s): 2006
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].
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).
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
110 107 7 3 3 5 9 9 8 1 8 Q 6 6U 3 4Q 0 1Q 0 5Q 4 7Q 3 5Q 0 2Q 4 6U 6 10Q 0 9
Sample Output
11423125
Author
shǎ崽
Source
HDOJ Monthly Contest – 2010.02.06
线段树区间合并
#include <iostream>#include <cstdio>#include <cstring>using namespace std;#define N 100005struct node{ int l,r,m; int ln,rn; int lsum,rsum,msum; int mid() { return (l+r)>>1; }}t[N<<2];int a[N];void pushup(int rt){ t[rt].lsum=t[rt<<1].lsum; t[rt].rsum=t[rt<<1|1].rsum; t[rt].ln=t[rt<<1].ln; t[rt].rn=t[rt<<1|1].rn; t[rt].msum=max(t[rt<<1].msum,t[rt<<1|1].msum); int ll=t[rt<<1].r-t[rt<<1].l+1; int rr=t[rt<<1|1].r-t[rt<<1|1].l+1; if(t[rt<<1].rn<t[rt<<1|1].ln) { if(t[rt<<1].lsum==ll) t[rt].lsum+=t[rt<<1|1].lsum; if(t[rt<<1|1].rsum==rr) t[rt].rsum+=t[rt<<1].rsum; t[rt].msum=max(t[rt].msum,t[rt<<1].rsum+t[rt<<1|1].lsum); }}void build(int l,int r,int rt){ t[rt].l=l; t[rt].r=r; if(l==r) { t[rt].ln=t[rt].rn=a[l]; t[rt].lsum=t[rt].rsum=t[rt].msum=1; return; } int m=t[rt].mid(); build(l,m,rt<<1); build(m+1,r,rt<<1|1); pushup(rt);}void update(int rt,int pos,int c){ if(t[rt].l==t[rt].r) { t[rt].ln=t[rt].rn=c; return; } int m=t[rt].mid(); if(pos<=m) update(rt<<1,pos,c); else update(rt<<1|1,pos,c); pushup(rt);}int query(int rt,int L,int R){ if(t[rt].l==L && t[rt].r==R) { return t[rt].msum; } int m=t[rt].mid(); if(R<=m) return query(rt<<1,L,R); else if(L>m) return query(rt<<1|1,L,R); else { int sum=0,m=t[rt].mid(); int ltmp=query(rt<<1,L,m); int rtmp=query(rt<<1|1,m+1,R); if(t[rt<<1].rn<t[rt<<1|1].ln) //注意：取最大值时要保证是在给定的区间[L,R]里面,左边，取min(全长，rsum），右边取min(全长,lsum) { sum=min(m-L+1,t[rt<<1].rsum)+min(R-m,t[rt<<1|1].lsum); } return max(max(ltmp,rtmp),sum); }}int main(){ int T,n,m,i; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); for(i=0;i<n;i++) { scanf("%d",&a[i]); } build(0,n-1,1); while(m--) { char op; int a,b; scanf(" %c%d%d",&op,&a,&b); if(op==‘U‘) update(1,a,b); else if(op==‘Q‘) printf("%d\n",query(1,a,b)); } } return 0;}
线段树 [HDU 3308] LCIS
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。