首页 > 代码库 > HDU 3308 线段树（区间合并）

HDU 3308 线段树（区间合并）

2024-07-13 06:20:55   229人阅读

LCIS

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


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
 
 
 
 
 
题目意思：
给两个数字n,m，分别代表数组长度和操作次数，下面一行是长度为n的序列，下面m行操作，共有两种操作：U a b 是把数组中a位置处的数字变为b（单点更新），Q a b  是输出区间[a,b]的最长连续子序列额长度。
 
 
典型的线段树区间合并了，其实我比较烦区间合并，考虑的条件有点多，稍不注意就错了，首先分析线段树结点所含元素种类：一个区间有左边界和右边界为l,r（线段树必不可少的），记录最长连续子序列的长度len，由于单点更新的时候区间的最长连续子序列的长度len可能发生变化，由子区间推出母区间，所以需要两个元素lmax,rmax即为区间包含左边界的连续子序列的长度、包含右边界的连续子序列的长度。
 
结点所含的元素种类确定下来了，就该进行操作了，建树就不说了（看代码吧），主要说一下up（向上更新）和query（输出） 。
up: 一个结点root的lmax和rmax显然分别等于左儿子的lmax和右儿子的rmax，len一会再说，怎么合并呢？当左儿子的右边界的值小于右儿子的左边界的值时，（在之前条件的情况下）如果左儿子的lmax包括了其右边界，那么root的lmax需要更新为tree[root*2].lmax+a[root*2+1].lmax，同理如果右儿子的rmax包括其左边界，那么root的rmax需要更新为tree[root*2+1].rmax+tree[root*2].rmax,  root的len  可能诞生在左边、右边、中间，那么取最大即可。
 
query: 主要讲一下所求的区间[a,b]既包含root的左儿子又包含其右儿子，那么可以用记忆话搜索用ln,rn分别记录root的左儿子和右儿子，区间[a,b]最长连续子序列可能诞生在ln中、rn中、或者ln和rn中，前两种情况好说，主要是最后一种，需要区间合并，合并方法和up函数同出一辙。
 
下面看代码：
  1 #include <cstdio>  2 #include <cstring>  3 #include <algorithm>  4 #include <iostream>  5 using namespace std;  6 #define N 100005  7 #define ll root*2  8 #define rr root*2+1  9  10 int num[N]; 11 int n, m; 12  13  14 struct node{ 15     int l, r; 16     int lmax, rmax; 17     int len; 18 }a[N*4]; 19  20  21 void pushup(int root){ 22     if(a[root].l==a[root].r) return; 23     a[root].lmax=a[ll].lmax; 24     a[root].rmax=a[rr].rmax; 25     a[root].len=max(a[ll].len,a[rr].len); 26      27     if(num[a[ll].r]<num[a[rr].l]){ 28         if(a[ll].lmax==(a[ll].r-a[ll].l+1)) a[root].lmax=a[ll].lmax+a[rr].lmax; 29         if(a[rr].rmax==(a[rr].r-a[rr].l+1)) a[root].rmax=a[rr].rmax+a[ll].rmax; 30         a[root].len=max(max(a[root].len,a[ll].rmax+a[rr].lmax),max(a[root].lmax,a[root].rmax)); 31     } 32 } 33  34 void build(int left,int right,int root){ 35     a[root].l=left; 36     a[root].r=right; 37     if(left==right){ 38         a[root].len=1; 39         a[root].lmax=a[root].rmax=1; 40         return ; 41     } 42     int mid=(left+right)/2; 43     build(left,mid,root*2); 44     build(mid+1,right,root*2+1); 45     pushup(root); 46 } 47  48 void update(int p,int val,int root){ 49     if(a[root].l==p&&a[root].r==p){ 50         num[p]=val; 51         return ; 52     } 53     int mid=(a[root].l+a[root].r)/2; 54     if(p<=mid) update(p,val,ll); 55     else update(p,val,rr); 56     pushup(root); 57 } 58  59 node query(int left,int right,int root){ 60     node n1, l1, r1; 61     if(a[root].l==left&&a[root].r==right){ 62         n1.lmax=a[root].lmax; 63         n1.rmax=a[root].rmax; 64         n1.len=a[root].len; 65         return n1; 66     } 67     if(left>=a[rr].l) return query(left,right,rr); 68     else if(right<=a[ll].r) return query(left,right,ll); 69     else{                                               //所求的连续子序列在中间，需要区间合并  70         int mid=(a[root].l+a[root].r)/2; 71         l1=query(left,mid,ll); 72         r1=query(mid+1,right,rr); 73         n1.lmax=l1.lmax; 74         n1.rmax=r1.rmax; 75         n1.len=max(l1.len,r1.len); 76         if(num[mid]<num[mid+1]){ 77             if(l1.lmax==(mid-left+1)) n1.lmax+=r1.lmax; 78             if(r1.rmax==(right-mid)) n1.rmax+=l1.rmax; 79             n1.len=max(max(n1.len,l1.rmax+r1.lmax),max(n1.lmax,n1.rmax)); 80         } 81         return n1; 82     } 83 } 84  85 main() 86 { 87     int t, i, j, k, x, y; 88     char c[5]; 89     cin>>t; 90     while(t--){ 91         cin>>n>>m; 92         for(i=1;i<=n;i++) scanf("%d",&num[i]); 93         build(1,n,1); 94         while(m--){ 95              96             scanf("%s %d %d",c,&x,&y); 97             if(strcmp(c,"U")==0){ 98                 update(x+1,y,1); 99             }100             else{101                 printf("%d\n",query(x+1,y+1,1).len);102             }103         }104     }105 }

 

 
 


联系
我们