首页 > 代码库 > hdu 3308 线段树 区间合并+单点更新+区间查询
hdu 3308 线段树 区间合并+单点更新+区间查询
LCIS
Time Limit: 6000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 6592 Accepted Submission(s): 2866
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<bits/stdc++.h>using namespace std;#define ll long long#define pi (4*atan(1.0))const int N=1e5+10,M=4e6+10,inf=1e9+10;struct is{ int l,r; int lm,mm,rm;}tree[N<<2];int val[N];void buildtree(int l,int r,int pos){ tree[pos].l=l; tree[pos].r=r; if(l==r) { tree[pos].lm=tree[pos].rm=tree[pos].mm=1; return; } int mid=(l+r)>>1; buildtree(l,mid,pos<<1); buildtree(mid+1,r,pos<<1|1); tree[pos].lm=tree[pos<<1].lm; tree[pos].rm=tree[pos<<1|1].rm; if(val[tree[pos<<1].r]<val[tree[pos<<1|1].l]) tree[pos].mm=max(tree[pos<<1].mm,max(tree[pos<<1|1].mm,tree[pos<<1].rm+tree[pos<<1|1].lm)); else tree[pos].mm=max(tree[pos<<1].mm,tree[pos<<1|1].mm); if(val[tree[pos<<1].r]<val[tree[pos<<1|1].l]&&tree[pos<<1].lm==tree[pos<<1].r-tree[pos<<1].l+1) tree[pos].lm+=tree[pos<<1|1].lm; if(val[tree[pos<<1].r]<val[tree[pos<<1|1].l]&&tree[pos<<1|1].rm==tree[pos<<1|1].r-tree[pos<<1|1].l+1) tree[pos].rm+=tree[pos<<1].rm;}void update(int point,int pos){ if(tree[pos].l==tree[pos].r) return; int mid=(tree[pos].r+tree[pos].l)>>1; if(point>mid) update(point,pos<<1|1); else update(point,pos<<1); tree[pos].lm=tree[pos<<1].lm; tree[pos].rm=tree[pos<<1|1].rm; if(val[tree[pos<<1].r]<val[tree[pos<<1|1].l]) tree[pos].mm=max(tree[pos<<1].mm,max(tree[pos<<1|1].mm,tree[pos<<1].rm+tree[pos<<1|1].lm)); else tree[pos].mm=max(tree[pos<<1].mm,tree[pos<<1|1].mm); if(val[tree[pos<<1].r]<val[tree[pos<<1|1].l]&&tree[pos<<1].lm==tree[pos<<1].r-tree[pos<<1].l+1) tree[pos].lm+=tree[pos<<1|1].lm; if(val[tree[pos<<1].r]<val[tree[pos<<1|1].l]&&tree[pos<<1|1].rm==tree[pos<<1|1].r-tree[pos<<1|1].l+1) tree[pos].rm+=tree[pos<<1].rm;}is query(int L,int R,int pos){ if(tree[pos].l==L&&tree[pos].r==R) return tree[pos]; int mid=(tree[pos].l+tree[pos].r)>>1; if(mid<L) return query(L,R,pos<<1|1); else if(mid>=R) return query(L,R,pos<<1); else { is a=query(L,mid,pos<<1); is b=query(mid+1,R,pos<<1|1); is ans; ans.l=a.l,ans.r=b.r; ans.lm=a.lm; ans.rm=b.rm; if(val[a.r]<val[b.l]) ans.mm=max(a.mm,max(b.mm,a.rm+b.lm)); else ans.mm=max(a.mm,b.mm); if(val[a.r]<val[b.l]&&a.lm==a.r-a.l+1) ans.lm+=b.lm; if(val[a.r]<val[b.l]&&b.rm==b.r-b.l+1) ans.rm+=a.rm; return ans; }}char a[10];int main(){ int T; scanf("%d",&T); while(T--) { int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&val[i]); buildtree(1,n,1); while(m--) { int l,r; scanf("%s%d%d",a,&l,&r); l++; if(a[0]==‘U‘) val[l]=r,update(l,1); else r++,printf("%d\n",query(l,r,1).mm); } } return 0;}
hdu 3308 线段树 区间合并+单点更新+区间查询
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。