频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
HDU 3308 最长上升连续子序列 (线段树)
2012-12-25 13:27:36      个评论      
收藏   我要投稿
[cpp] view plaincopy

题意不用说了,此题是传说中的  “傻仔哥”  出的,虽然不知教主真名,但是还是看着他的线段树长大的....  

  

Code:  

  

#include<iostream>  

#include<cstdio>  

#include<string>  

#include<cmath>  

#define lson l,mid,rt<<1  

#define rson mid+1,r,rt<<1|1  

#define manx 100050  

using namespace std;  

int root[manx<<2],lm[manx<<2],rm[manx<<2],a[manx];  

void up(int l,int r,int rt){  

    lm[rt] = lm[rt<<1];  

    rm[rt] = rm[rt<<1|1];  

    root[rt] = max(root[rt<<1],root[rt<<1|1]);  

    int mid = (l+r)>>1;  

    if(a[mid+1]>a[mid]){  

        if(lm[rt<<1] == mid-l+1) lm[rt] += lm[rt<<1|1];  

        if(rm[rt<<1|1] == r-mid) rm[rt] += rm[rt<<1];  

        root[rt] = max(root[rt],lm[rt<<1|1]+rm[rt<<1]);  

    }  

}  

void make(int l,int r,int rt){  

    if(l==r){  

        lm[rt] = rm[rt] = root[rt] = 1;  

        return ;  

    }  

    int mid = (l+r)>>1;  

    make(lson);  

    make(rson);  

    up(l,r,rt);  

 //   cout<<l<<" "<<r<<" "<<rt<<" "<<root[rt]<<endl;  

}  

int query(int l,int r,int rt,int ll,int rr){  

    if(ll<=l && rr>=r){  

        return root[rt];  

    }  

    int mid=(l+r)>>1;  

    if(rr<=mid) return query(lson,ll,rr);  

    else if(ll>mid) return query(rson,ll,rr);  

    else {  

        int t1 = query(lson,ll,mid);  

        int t2 = query(rson,mid+1,rr);  

        int t = max(t1,t2);  

        if(a[mid] < a[mid+1]){  

            t1 = min(rm[rt<<1],mid-ll+1);  ////  防止越界的情况发生   

            t2 = min(lm[rt<<1|1],rr-mid);  

            t1 += t2;  

        }  

        return max(t,t1);  

    }  

}  

void update(int l,int r,int rt,int p,int q){  

    if(l==r && r==p){  

        a[l] = q;  

        return ;  

    }  

    int mid = (l+r)>>1;  

    if(p<=mid) update(lson,p,q);  

    else  update(rson,p,q);  

    up(l,r,rt);  

}  

int main(){  

    int t,n,m;  

    scanf("%d",&t);  

    while(t--){  

        scanf("%d%d",&n,&m);  

        for(int i=1;i<=n;i++)  

            scanf("%d",&a[i]);  

        make(1,n,1);  

        int p,q;  

        char ch[5];  

        for(int i=1;i<=m;i++){  

            scanf("%s%d%d",ch,&p,&q);  

            if(ch[0]=='Q'){  

                p++,q++;  

                int flag = query(1,n,1,p,q);  

                printf("%d\n",flag);  

            }  

            if(ch[0]=='U'){  

                p++;  

                update(1,n,1,p,q);  

            }  

        }      

    }  

}  

点击复制链接 与好友分享!回本站首页
相关TAG标签 线段 序列
上一篇:C++程序员Python notes
下一篇:POJ 3080 Blue Jeans
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站