hdu3308 LCIS(线段树区间合并)

题目链接：hdu3308

/*hdu3308 LCIS 线段树区间合并
题目大意：
    求一段区间内的连续最长
思路：
    记录以区间左端点开始的LCIS，以区间右端点结尾的LCIS以及整个区间的LCIS，
区间左端点的数和区间右端点的数。
更新和建树操作都应更到叶子节点，只有叶子节点的信息时可以直接得出，然后
递归回到父节点，父节点可以根据左右孩子的信息来更新自己
*/
#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        using namespace std; #define lson l, m, rt<<1 #define rson m+1, r, rt<<1|1 const int N = 200005; struct node { int lnum, rnum;//区间最左端的数和最右端的数 int llen;//以左端点开始的连续最长 int rlen;//以右端点结束的连续最长 int mlen;//区间内的连续最长 }s[N<<2]; void pushup(int rt, int m) { s[rt].lnum = s[rt<<1].lnum; s[rt].rnum = s[rt<<1|1].rnum; s[rt].llen = s[rt<<1].llen; s[rt].rlen = s[rt<<1|1].rlen; s[rt].mlen = max(s[rt<<1].mlen, s[rt<<1|1].mlen); if(s[rt<<1].rnum < s[rt<<1|1].lnum)//左儿子的右端点<右儿子的左端点 { if(s[rt].llen == m - (m>>1))//左儿子表示的区间里的所有数，连续递增 s[rt].llen += s[rt<<1|1].llen; if(s[rt].rlen == (m>>1))//右儿子表示的区间里的所有数，连续递增 s[rt].rlen += s[rt<<1].rlen; s[rt].mlen = max(s[rt<<1].rlen + s[rt<<1|1].llen, s[rt].mlen);//左儿子的右连续长度+右儿子的左连续长度 } } void build(int l, int r, int rt) { s[rt].llen = s[rt].rlen = s[rt].mlen = 1; if(l == r) { scanf("%d",&s[rt].lnum); s[rt].rnum = s[rt].lnum; return; } int m = (l+r) >





> 1; build(lson); build(rson); pushup(rt, r-l+1); } void update(int pos, int num, int l, int r, int rt) { if(l == pos && pos == r) { s[rt].llen = s[rt].rlen = s[rt].mlen = 1; s[rt].lnum = s[rt].rnum = num; return; } int m = (l+r) >> 1; if(pos <= m) update(pos, num, lson); else update(pos, num, rson); pushup(rt, r-l+1); } int query(int L, int R, int l, int r, int rt) { if(L <= l && r <= R) { return s[rt].mlen; } int m = (l+r) >> 1; int ans = 0; if(L <= m) ans = max(ans, query(L, R, lson)); if(m < R) ans = max(ans, query(L, R, rson)); if(s[rt<<1].rnum < s[rt<<1|1].lnum) ans = max(ans, min(m-L+1,s[rt<<1].rlen) + min(R-m, s[rt<<1|1].llen) ); return ans; } int main() { int T,n,m; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); build(1, n, 1); char a[2]; int x,y; while(m--) { scanf("%s%d%d",a,&x,&y); if(a[0] == 'Q') printf("%d\n",query(x+1, y+1, 1, n, 1)); if(a[0] == 'U') update(x+1, y, 1, n, 1); } } return 0; }