2017多校训练2 HDU 6047 Maximum Sequence

原题连接: :point_right:Maximum Sequence
题意: 给定一个长度为n的a数组和b数组,要求a[n+1]…a[2*n]的最大总和。 限制条件为ai≤max{aj-j│bk≤j<i}。
题解: 两种方法,一种是线段树,另一种是第一次记录maxv数组,记录每个i到maxindex(A)的最大值,然后动态更新.
github:
1.线段树法: :point_right:1003_Range_Tree.cpp
2.暴力动态更新法: :point_right:1003.cpp

///线段树法
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod=1e9+7;
const int maxnode=2000050;

int b[maxnode],N;
int maxv[maxnode];

void build(int o,int l,int r){
    if(l==r){
        if(l>N) return;///预先分配2*N个结点
        scanf("%d",&maxv[o]);maxv[o]-=l;
        return;
    }
    int mid=(l+r)>>1;
    build(o<<1,l,mid);
    build(o<<1|1,mid+1,r);
    maxv[o]=max(maxv[o<<1],maxv[o<<1|1]);
}

int query(int o,int l,int r,int ll,int rr){
    if(l>=ll&&r<=rr) return maxv[o];
    int ma=-1,mid=(l+r)>>1;
    if(mid>=ll) ma=max(ma,query(o<<1,l,mid,ll,rr));
    if(rr>mid) ma=max(ma,query(o<<1|1,mid+1,r,ll,rr));
    return ma;
}

void update(int o,int l,int r,int p,int val){
    if(l==r){
        maxv[o]=val;
        return;
    }
    int mid=(l+r)>>1;
    if(p<=mid)update(o<<1,l,mid,p,val);
    else update(o<<1|1,mid+1,r,p,val);
    maxv[o]=max(maxv[o<<1],maxv[o<<1|1]);
}

int main(){
    while(~scanf("%d",&N)&&N){
        build(1,1,2*N);
        for(int i=1;i<=N;++i) scanf("%d",&b[i]);
        sort(b+1,b+1+N);
        LL ans=0;
        for(int i=N+1;i<=2*N;++i){
            int k=query(1,1,2*N,b[i-N],i-1);
            update(1,1,2*N,i,k-i);
            ans=(ans+k)%mod;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

///HDU 6047 暴力动态更新法
#include<bits/stdc++.h>
using namespace std;
const int maxn=500000+50;
const int mod=1e9+7;
int N;
int a[maxn],b[maxn],maxa[maxn];

int main(){
    while(~scanf("%d",&N)&&N){
        for(int i=1;i<=N;++i){
            int aa;
            scanf("%d",&aa);
            a[i]=aa-i;
        }
        maxa[N]=a[N];
        for(int i=N-1;i>=1;--i) maxa[i]=max(maxa[i+1],a[i]);
        for(int i=1;i<=N;++i) scanf("%d",&b[i]);
        sort(b+1,b+1+N);
        long long ans=0;
        ans=(ans+maxa[b[1]])%mod;
        int t=maxa[b[1]]-N-1;
        for(int i=2;i<=N;++i){
            maxa[b[i]]=max(maxa[b[i]],t);
            ans=(ans+maxa[b[i]])%mod;
            t=max(t,maxa[b[i]]-N-1);
        }
        printf("%lld\n",ans%mod);
    }
    return 0;
}

算法学习-线段树

【概念】

线段树是擅长处理区间的,且是一颗完美二叉树(Perfect Binary Tree),树上每一个节点都维护一个区间,根维护的是整个区间,每个节点维护的是父亲的区间二等分后的其中一个子区间。当有n个元素时,对区间的操作可以在O(log n)的时间内完成.

以下我们以实现了Range Minimum Query(RMQ,范围最小值查询)操作的线段树为例,进行说明.

【基于线段树的RMQ的结构】

Continue reading “算法学习-线段树”