随笔 - 97, 文章 - 22, 评论 - 81, 引用 - 0
数据加载中……

HDU 3308 LCIS

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3308

/*
题意:
    给出一个长度为N(N <= 100000)的数列,然后是两种操作:
U A B: 将第A个数替换为B (下标从零开始)
Q A B: 输出区间[A, B]的最长连续递增子序列
注意:操作的数目m <= 100000。

解法:
线段树

思路:
    做惯了区间最值、求和、修改、染色的等问题,这题算比较新颖
的了,由这题可以看出线段树的一般解法,因为这题要求保存的信息
比较多,每个线段树的结点要求保存的信息有以下几个:

    int lMax;       // 包含结点左端点的最长连续递增子序列的长度
    int rMax;       // 包含结点右端点的最长连续递增子序列的长度
    int Max;        // 当前结点的最长连续递增子序列的长度
    int lVal, rVal; // 当前结点管辖的区间左右端点的数值
    int l, r;       // 当前结点管辖的区间

我们用以下函数从左右儿子中得到当前结点的信息:
void UpdateBy(Tree* ls, Tree* rs);
之所以把它写成函数是因为这里的处理比较麻烦,很容易出错,并且需要
调用多次,这个函数的作用就是通过左右儿子的信息填充本身的信息。

lVal、rVal、l、r等信息比较容易求得。
lMax和rMax的值就比较麻烦了,需要分情况讨论(下面的len表示区间长度):
1. 左儿子最右边的值 < 右儿子最左边的值

    lMax = (左儿子的lMax == 左儿子的len) ? 左儿子的len + 右儿子的lMax : 左儿子的lMax;
    rMax = (右儿子的rMax == 右儿子的len) ? 右儿子的len + 左儿子的rMax : 右儿子的rMax;
    Max  = MAX(左儿子的rMax + 右儿子的lMax, 左儿子的Max, 右儿子的Max, lMax, rMax);

2. 左儿子最右边的值 >= 右儿子最左边的值

    lMax = 左儿子的lMax;
    rMax = 右儿子的rMax;
    Max  = MAX(左儿子的Max, 右儿子的Max);

一开始读入的时候有一连串数字,需要建树,建树的时候每次回归时需要
将儿子的信息传递给父亲,调用UpdateBy(Tree* ls, Tree* rs)函数,每
次插入完毕后回归时,信息会更新,也需要调用。询问时,返回的也是一
个线段树结点,并且需要将答案合并,还是需要调用UpdateBy函数,所以
总的来说需要调用三次,把它写成一个函数还是势在必行的。
*/



#include 
<iostream>

using namespace std;

#define maxn 100010

struct Tree {
    
int lMax;       // 包含结点左端点的最长连续递增子序列
    int rMax;       // 包含结点右端点的最长连续递增子序列
    int Max;        // 当前结点的最长连续递增子序列
    int lVal, rVal; // 当前区间左右端点的值
    int l, r;       // 当前结点管辖的区间
    int son[2];

    
void clear() {
        son[
0= son[1= -1;
    }

    
void UpdateBy(Tree* ls, Tree* rs);
    
void Unit(int nl, int nr, int nv);
    
int len() {
        
return r - l + 1;
    }

}
T[maxn*4];
int root, tot;
int val[ maxn ];

int MAX(int a, int b) {
    
return a > b ? a : b;
}


int MAX(int a, int b, int c) {
    
return MAX(MAX(a, b), c);
}


int MAX(int a, int b, int c, int d) {
    
return MAX( MAX(a, b), MAX(c, d) );
}


void Tree::UpdateBy(Tree* ls, Tree* rs) {
    lVal 
= ls->lVal;
    rVal 
= rs->rVal;
    l    
= ls->l;
    r    
= rs->r;
    
if(ls->rVal < rs->lVal) {
        lMax 
= (ls->lMax == ls->len()) ? ls->len() + rs->lMax : ls->lMax;
        rMax 
= (rs->rMax == rs->len()) ? rs->len() + ls->rMax : rs->rMax;
        
        Max  
= MAX(ls->rMax + rs->lMax, ls->Max, rs->Max);
        Max  
= MAX(Max, lMax, rMax);

    }
else {
        lMax 
= ls->lMax;
        rMax 
= rs->rMax;
        Max  
= MAX(ls->Max, rs->Max);
    }

}


void Tree::Unit(int nl, int nr, int nv) {
    lMax 
= rMax = 1; Max = 1;
    lVal 
= rVal = nv;
    l 
= nl; r = nr;
}


int GetID(int& root) {
    
if(root == -1{
        root 
= tot++;
        T[root].clear();
    }

    
return root;
}


void Build(int& root, int l, int r) {
    GetID(root);
    
if(l == r) {
        T[root].Unit(l, r, val[l]);
        
return ;
    }

    
int mid = (l + r) >> 1;
    Build(T[root].son[
0], l, mid);
    Build(T[root].son[
1], mid+1, r);

    T[root].UpdateBy(
&T[ T[root].son[0] ], &T[ T[root].son[1] ]);
}


void Insert(int root, int nPos, int val) {
    
if(nPos < T[root].l || nPos > T[root].r)
        
return ;
    
if(T[root].l == nPos && nPos == T[root].r) {
        T[root].Unit(nPos, nPos, val);
        
return ;
    }

    Insert(T[root].son[
0], nPos, val);
    Insert(T[root].son[
1], nPos, val);

    T[root].UpdateBy(
&T[ T[root].son[0] ], &T[ T[root].son[1] ]);
}


Tree Query(
int root, int nl, int nr) {
    
if(nl > T[root].r || nr < T[root].l) {
        Tree tmp;
        tmp.Max 
= -1;
        
return tmp;
    }


    
if(nl <= T[root].l && T[root].r <= nr) {
        
return T[root];
    }

    Tree A, B;
    A 
= Query(T[root].son[0], nl, nr);
    B 
= Query(T[root].son[1], nl, nr);
    
if(A.Max == -1)
        
return B;
    
else if(B.Max == -1)
        
return A;
    
else {
        Tree X;
        X.UpdateBy(
&A, &B);
        
return X;
    }

}


int n, m;
int main() {
    
int t, i;
    scanf(
"%d"&t);

    
while(t--{
        scanf(
"%d %d"&n, &m);
        
for(i = 1; i <= n; i++{
            scanf(
"%d"&val[i]);
        }

        tot 
= 0;
        root 
= -1;
        Build(root, 
1, n);
        
while(m--{
            
char str[10];
            
int A, B;
            scanf(
"%s %d %d", str, &A, &B);
            
if(!strcmp(str, "U")) {
                Insert(root, A
+1, B);
            }
else {
                Tree tmp 
= Query(root, A+1, B+1);
                printf(
"%d\n", tmp.Max);
            }

        }

    }

    
return 0;
}

posted on 2011-04-01 02:36 英雄哪里出来 阅读(1979) 评论(2)  编辑 收藏 引用 所属分类: 线段树

评论

# re: HDU 3308 LCIS  回复  更多评论   

受教了!狂膜拜!
2011-08-15 10:36 | Now_I

# re: HDU 3308 LCIS  回复  更多评论   

新生,敢问,为什么这样区分是对的呢??
还是没有想明白,请大神解析一下。
1. 左儿子最右边的值 < 右儿子最左边的值

lMax = (左儿子的lMax == 左儿子的len) ? 左儿子的len + 右儿子的lMax : 左儿子的lMax;
rMax = (右儿子的rMax == 右儿子的len) ? 右儿子的len + 左儿子的rMax : 右儿子的rMax;
Max = MAX(左儿子的rMax + 右儿子的lMax, 左儿子的Max, 右儿子的Max, lMax, rMax);

谢谢了。
2013-04-27 18:57 | ni hao

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理