HDU 3308 LCIS(线段树区间合并） - c++编程基础

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 5).
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

比较普通的区间合并题型吧。记录左右段的，然后合并时根据端点情况即可。

#include
   
    
#include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
          
            #include
            #include
            
              #include
             
               using namespace std; #define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i ) #define REP( i , n ) for ( int i = 0 ; i < n ; ++ i ) #define CLEAR( a , x ) memset ( a , x , sizeof a ) typedef long long LL; typedef pair
              
               pil; const int INF = 0x3f3f3f3f; const int maxn=1e5+100; int lsum[maxn<<2],rsum[maxn<<2]; int mm[maxn<<2],sum[maxn]; int t,n,m,x; void pushup(int rs,int l,int r) { lsum[rs]=lsum[rs<<1]; rsum[rs]=rsum[rs<<1|1]; mm[rs]=max(mm[rs<<1],mm[rs<<1|1]); int mid=(l+r)>>1; if(sum[mid]
               
                >1; build(rs<<1,l,mid); build(rs<<1|1,mid+1,r); pushup(rs,l,r); } void update(int x,int c,int l,int r,int rs) { if(l==r) { sum[x]=c; return ; } int mid=(l+r)>>1; if(x<=mid) update(x,c,l,mid,rs<<1); else update(x,c,mid+1,r,rs<<1|1); pushup(rs,l,r); } int query(int x,int y,int l,int r,int rs) { if(l>=x&&r<=y) return mm[rs]; int mid=(l+r)>>1;int res=0; if(x<=mid) res=max(res,query(x,y,l,mid,rs<<1)); if(y>mid) res=max(res,query(x,y,mid+1,r,rs<<1|1)); if(sum[mid]
                
                 mid) res=max(res,min(mid-x+1,rsum[rs<<1])+min(y-mid,lsum[rs<<1|1])); return res; } int main() { int x,y;char str[10]; scanf("%d",&t); while(t--) { CLEAR(mm,0);CLEAR(lsum,0);CLEAR(rsum,0); scanf("%d%d",&n,&m); REPF(i,1,n) scanf("%d",&sum[i]); build(1,1,n); while(m--) { scanf("%s%d%d",str,&x,&y); if(str[0]=='U') update(x+1,y,1,n,1); else { int ans=query(x+1,y+1,1,n,1); printf("%d\n",ans); } } } return 0; }