Time Limit: 6000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 5912 Accepted Submission(s): 2563
给你n个数组成的序列(序列中编号从0到n-1),有q次操作。
操作1——Q a b,让你输出区间[a, b]里面最长的连续递增序列的长度;
操作2——U a b,修改序列第a个数为b。
出了点小问题错了半天;
刚开始理解错了,是单调上升序列;1 3 5 7也算;
区间合并
代码:
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<vector> using namespace std; const int INF=0x3f3f3f3f; #define mem(x,y) memset(x,y,sizeof(x)) #define SI(x) scanf("%d",&x) #define PI(x) printf("%d",x) #define SD(x,y) scanf("%lf%lf",&x,&y) #define P_ printf(" ") #define ll root<<1 #define rr root<<1|1 #define lson ll,l,mid #define rson rr,mid+1,r typedef long long LL; const int MAXN=100010; struct Node{ int len,lv,rv,lsum,rsum,sum; Node init(int l,int r){ scanf("%d",&lv);rv=lv; lsum=sum=rsum=1; } }; Node tree[MAXN<<2]; /*void print(int root,int l,int r){ int mid=(l+r)>>1; if(l==r){ printf("%d %d\n",tree[root].lv,tree[root].rv);return; } print(lson);print(rson); }*/ void pushup(int root){ tree[root].lsum=tree[ll].lsum; tree[root].rsum=tree[rr].rsum; tree[root].lv=tree[ll].lv; tree[root].rv=tree[rr].rv; tree[root].sum=max(tree[ll].sum,tree[rr].sum); if(tree[ll].rv<tree[rr].lv){ if(tree[ll].lsum==tree[ll].len)tree[root].lsum+=tree[rr].lsum; if(tree[rr].rsum==tree[rr].len)tree[root].rsum+=tree[ll].rsum; tree[root].sum=max(tree[root].sum,tree[ll].rsum+tree[rr].lsum); } } void build(int root,int l,int r){ tree[root].len=r-l+1;//放在里面了。。。错了 if(l==r){ tree[root].init(l,r); return ; } int mid=(l+r)>>1; build(lson); build(rson); pushup(root); } void update(int root,int l,int r,int A,int B){ int mid=(l+r)>>1; if(l==A&&r==A){ tree[root].lv=tree[root].rv=B; return; } if(mid>=A)update(lson,A,B); else update(rson,A,B); pushup(root); } int query(int root,int l,int r,int A,int B){ if(l>=A&&r<=B)return tree[root].sum; int mid=(l+r)>>1; int ans=0; if(mid>=A)ans=max(ans,query(lson,A,B));//多加了return错了半天;;;; if(mid<B)ans=max(ans,query(rson,A,B));// if(tree[ll].rv<tree[rr].lv) ans=max(ans,min(mid-A+1,tree[ll].rsum)+min(B-mid,tree[rr].lsum)); //以免超过查询区间;因为里面的lsum,rsum分别维护的左右最大连续上升序列; return ans; } int main(){ int T,N,M; char s[5]; int A,B; SI(T); while(T--){ SI(N);SI(M); build(1,1,N); while(M--){ scanf("%s%d%d",s,&A,&B); A++; if(s[0]==‘Q‘){ B++; printf("%d\n",query(1,1,N,A,B)); } else update(1,1,N,A,B); // print(1,1,N); } } return 0; }
原文:http://www.cnblogs.com/handsomecui/p/5202622.html