HDU 5306 Gorgeous Sequence

发布于 2018-11-18  315 次阅读


题目链接

题目描述

(本人喜欢用 Vjudge 所以就放那里的链接啦。
给定一个序列,要求实现区间求最大值,区间求和,区间对一个数取min。

解题报告

开始挖十一集训的坟了......
这一题是吉司机线段树模板题的简化版本。
大家都会维护最大值和和,怎么实现那个取min的操作呢?
我们考虑对于每个区间都先维护出这个区间的最大值 max,次大值 se,最大值出现的次数 cnt。
这样在覆盖的时候分类讨论一下,设这个区间要对x整体取min:
如果当前区间 $max \leq x$ 就不用继续处理了因为这个区间不会改变;
如果当前区间 $ max \geq x $ 并且 $se \leq x $ 那么只需要将这个区间的最大值改一下就可以了。
否则就递归左右子树继续找,最后合并一下就可以了。
合并也是要分类讨论的 $qwq$.
合并注意下要判断两边的max相等的情况,这时候的cnt和se取值都与一般情况不同。
还有一个小问题:我不知道为什么我如果去掉注释里的CLR函数(即memset) 就会提示我MLE?我十分的疑惑,如果有知道的神犇请在评论里告诉我 $qwq$ 谢谢。
另外这个题目还有一个 进阶版本,按照这种分类讨论操作的思想写就可以了,只不过可能代码量会 长一些。

代码实现

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

#define Re register
#define LL long long
#define CLR(a,b) memset(a,b,sizeof(a))
#define FOR(i,a,b) for(Re int i = a;i <= b;++i)
#define ROF(i,a,b) for(Re int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 1000000+5;

struct SegmentTree *New(int ,int ,SegmentTree *,SegmentTree *);

struct SegmentTree{
    int l,r,max,se,cnt;
    LL sum;
    SegmentTree *lc,*rc;
    
    static SegmentTree *build(int l,int r){
        int mid = (l + r) >> 1;
        return l == r ? New(l,r,NULL,NULL) : New(l,r,build(l,mid),build(mid+1,r));
    }
    
    void pushup(){
        if(lc->max > rc->max){
            max = lc->max;
            se = std::max(lc->se,rc->max);
            cnt = lc->cnt;
        }
        if(lc->max == rc->max){
            max = lc->max;
            se = std::max(lc->se,rc->se);
            cnt = lc->cnt + rc->cnt;
        }
        if(lc->max < rc->max){
            max = rc->max;
            se = std::max(lc->max,rc->se);
            cnt = rc->cnt;
        }
        sum = lc->sum + rc->sum;
    }
    
    void cover(int delta){
        if(max <= delta) return;
        sum += 1ll*cnt*(delta-max);
        max = delta;
    }
    
    void pushdown(){
        lc->cover(max);
        rc->cover(max);
    }
    
    void update(int pos,int x){
        if(l == r){
            max = sum = x;
            se = -1;cnt = 1;
            return;
        }
        int mid = (l + r) >> 1;
        if(pos <= mid) lc->update(pos,x);
        else rc->update(pos,x);
        pushup();
    }
    
    void modify(int L,int R,int x){
        if(x >= max) return;
        if(L == l && R == r && x > se){
            cover(x);
            return;
        }
        pushdown();
        int mid = (l + r) >> 1;
        if(R <= mid) lc->modify(L,R,x);
        else if(L > mid) rc->modify(L,R,x);
        else lc->modify(L,mid,x),rc->modify(mid+1,R,x);
        pushup();
    }
    
    int qmax(int L,int R){
        if(L == l && R == r) return max;
        pushdown();
        int mid = (l + r) >> 1;
        if(R <= mid) return lc->qmax(L,R);
        if(L > mid) return rc->qmax(L,R);
        return std::max(lc->qmax(L,mid),rc->qmax(mid+1,R));
    }
    
    LL qsum(int L,int R){
        if(L == l && R == r) return sum;
        pushdown();
        int mid = (l + r) >> 1;
        if(R <= mid) return lc->qsum(L,R);
        if(L > mid) return rc->qsum(L,R);
        return lc->qsum(L,mid) + rc->qsum(mid+1,R);
    }
}pool[MAXN<<2],*frog = pool,*segt;

SegmentTree *New(int l,int r,SegmentTree *lc,SegmentTree *rc){
    SegmentTree *ret = ++frog;
    ret->l = l;ret->r = r;ret->lc = lc;ret->rc = rc;
    ret->max = ret->se = -1;ret->cnt = ret->sum = 0;
    return ret;
}

inline void Solve(){
    frog = pool;//CLR(pool,0);
    int N,M;scanf("%d%d",&N,&M);
    segt = SegmentTree::build(1,N);
    FOR(i,1,N){
        int x;scanf("%d",&x);
        segt->update(i,x);
    }
    while(M--){
        int opt,l,r;
        scanf("%d%d%d",&opt,&l,&r);
        if(opt == 0){
            int t;scanf("%d",&t);
            segt->modify(l,r,t);
        }
        if(opt == 1){
            printf("%d\n",segt->qmax(l,r));
        }
        if(opt == 2){
            printf("%lld\n",segt->qsum(l,r));
        }
    }
}

int main(){
    int T;scanf("%d",&T);
    while(T--) Solve();
    return 0;
}

一个OIer。