精华内容
下载资源
问答
  • 一、区间最值操作 例题一、 Gorgeous Sequence 本题要求我们实现三个操作 对于第二种和第三种操作我们是已经知道如何写了。 问题就在于第一种操作。 考虑第一种操作是取min 因此当我们这个区间内的最大值 1.如果...

    前提知识

    基本的线段树写法:
    洛谷线段树1
    洛谷线段树2

    以下是正文

    一、区间最值操作

    在这里插入图片描述

    例题一、

    Gorgeous Sequence

    本题要求我们实现三个操作
    在这里插入图片描述

    做法一、

    对于第二种和第三种操作我们是已经知道如何写了。

    问题就在于第一种操作。

    考虑第一种操作是取min
    因此当我们这个区间内的最大值 
    1.如果比给定的k来得小 那么我们不需要任何操作
    2.如果这个k<最大值 但是k > 第二大的值(以下称为次大值)
    那么我们只需要将最大值全部变成k,修改一下区间和即可.
    3.如果这个k<最大值 && k < 次大值 
    那么我们当前这个结点是处理不了的,直接push_down交给儿子结点
    

    Code

    #include <iostream>
    #include <cstring>
    #define lc (p<<1)
    #define rc (p<<1|1)
    using namespace std;
    typedef long long ll;
    const int N = 1100000;
    struct Node{
        int L,R,tag;//这个tag是维护区间最值操作的
        ll sum;
        int fir_big,sec_big;
        int fir_num;
    }tree[N*4];
    int a[N];
    inline void push_up(int);
    void build_tree(int l,int r,int p){
        //tag的取值是0~2^31-1 因此我们取-1
        tree[p].L=l,tree[p].R=r,tree[p].tag=-1;
        if(l==r){
            tree[p].sum=a[l];
            tree[p].fir_big=a[l];
            tree[p].sec_big=-1;
            tree[p].fir_num=1;
            return;
        }
        int mid = (l+r)>>1;
        build_tree(l,mid,lc);
        build_tree(mid+1,r,rc);
        push_up(p);
    }
    inline void push_up(int p){
        tree[p].sum=tree[lc].sum+tree[rc].sum;
        if(tree[lc].fir_big==tree[rc].fir_big){
            tree[p].fir_big=tree[lc].fir_big;
            tree[p].fir_num=tree[lc].fir_num+tree[rc].fir_num;
            tree[p].sec_big=max(tree[lc].sec_big,tree[rc].sec_big);
        }else if(tree[lc].fir_big>tree[rc].fir_big){
            tree[p].fir_big=tree[lc].fir_big;
            tree[p].fir_num=tree[lc].fir_num;
            tree[p].sec_big=max(tree[lc].sec_big,tree[rc].fir_big);
        }else{
            tree[p].fir_big=tree[rc].fir_big;
            tree[p].fir_num=tree[rc].fir_num;
            tree[p].sec_big=max(tree[rc].sec_big,tree[lc].fir_big);
        }
    }
    inline void update(int p,int cnt_val){
        if(cnt_val<tree[p].fir_big){
            //最大值全部变成cnt_val
            tree[p].sum+=(1ll*cnt_val-tree[p].fir_big)*tree[p].fir_num;
            tree[p].fir_big=tree[p].tag=cnt_val;
        }
    }
    inline void push_down(int p){
        if(~tree[p].tag){
            update(lc,tree[p].tag);
            update(rc,tree[p].tag);
            tree[p].tag=-1;
        }
    }
    void modify(int p,int l,int r,int cnt_val){
        if(tree[p].L>r||tree[p].R<l||tree[p].fir_big<=cnt_val) return;
        if(tree[p].L>=l&&tree[p].R<=r&&tree[p].sec_big<cnt_val){
            update(p,cnt_val);
            return;
        }
        push_down(p);
        modify(lc,l,r,cnt_val);
        modify(rc,l,r,cnt_val);
        push_up(p);
    }
    int queryMax(int p,int l,int r){
        if(tree[p].L>r||tree[p].R<l) return 0;
        if(tree[p].L>=l&&tree[p].R<=r){
            return tree[p].fir_big;
        }
        push_down(p);
        return max(queryMax(lc,l,r),queryMax(rc,l,r));
    }
    ll querySum(int p,int l,int r){
        if(tree[p].L>r||tree[p].R<l) return 0;
        if(tree[p].L>=l&&tree[p].R<=r){
            return tree[p].sum;
        }
        push_down(p);
        return querySum(lc,l,r)+querySum(rc,l,r);
    }
    #undef lc
    #undef rc
    int read(){
    	int x=0; char ch=0;
    	while (!isdigit(ch)) ch=getchar();
    	while (isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48), ch=getchar();
    	return x;
    }
    #if 0
    这份代码完成三个功能
    1.区间最小值操作
    2.求区间最大值
    3.求区间和
    #endif // 0
    int main()
    {
        int t,n,m;
        t=read();
        while(t--){
            n=read();
            m=read();
            for(int i=1;i<=n;i++){
               a[i]=read();
            }
            build_tree(1,n,1);
            for(int i=1;i<=m;i++){
                int op,x,y,t;
                op=read();
                if(op==0){
                    x=read();
                    y=read();
                    t=read();
                    modify(1,x,y,t);
                }else if(op==1){
                    x=read();
                    y=read();
                    printf("%d\n",queryMax(1,x,y));
                }else{
                    x=read();
                    y=read();
                    printf("%lld\n",querySum(1,x,y));
                }
            }
        }
        return 0;
    }
    
    

    做法二、

    2021.9.8复习更新另一个代码;
    这份代码和上面那种做法不同点在于,他不是维护一个改变的tag,而是维护一个加法的tag;

    按照例题二的思路,我们将值分为三种,最大值、次大值、其他值;

    维护两个标记,最大值的加法标记,其他值的加法标记;

    #include <iostream>
    #include <cstring>
    
    #define lc (p<<1)
    #define rc (p<<1|1)
    
    using namespace std;
    
    typedef long long ll;
    
    const int N = 1000010;
    
    struct Node{
        int l,r,mx,sec_mx,mx_num;
        int mx_tag,other_tag;
        ll sum;
    }tr[N<<2];
    
    int a[N],t,n,m;
    void push_down(int p);
    int read()
    {
        int x=0; char ch=0;
        while (!isdigit(ch)) ch=getchar();
        while (isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48), ch=getchar();
        return x;
    }
    void push_up(int p){
        tr[p].sum = tr[lc].sum + tr[rc].sum;
        if(tr[lc].mx == tr[rc].mx){
            tr[p].mx = tr[lc].mx;
            tr[p].mx_num = tr[lc].mx_num + tr[rc].mx_num;
            tr[p].sec_mx = max(tr[lc].sec_mx,tr[rc].sec_mx);
        }else if(tr[lc].mx > tr[rc].mx){
            tr[p].mx = tr[lc].mx;
            tr[p].mx_num = tr[lc].mx_num;
            tr[p].sec_mx = max(tr[lc].sec_mx,tr[rc].mx);
        }else{
            tr[p].mx = tr[rc].mx;
            tr[p].mx_num = tr[rc].mx_num;
            tr[p].sec_mx = max(tr[rc].sec_mx,tr[lc].mx);
        }
    }
    void build(int p,int l,int r){
        tr[p].l = l,tr[p].r = r;
        tr[p].sec_mx = -1;//因为数据范围是从0开始的
        tr[p].mx_tag = tr[p].other_tag = 0;
        if(l == r){
            tr[p].sum = tr[p].mx = a[l];
            tr[p].mx_num = 1;
            return;
        }
        int mid = (l+r) >> 1;
        build(lc,l,mid);
        build(rc,mid+1,r);
        push_up(p);
    }
    //给这个节点的最大值、其他值加上某些数
    void node_update_fun(int p,int mxk,int otherk){
        tr[p].sum += 1ll*mxk*tr[p].mx_num + 1ll*(tr[p].r-tr[p].l+1-tr[p].mx_num)*otherk;
        if(tr[p].sec_mx != -1) tr[p].sec_mx += otherk;
        tr[p].mx  += mxk;
        tr[p].mx_tag += mxk;
        tr[p].other_tag += otherk;
    }
    void range_min_fun(int p,int l,int r,int k){
        if(k>=tr[p].mx) return;
        if(tr[p].l>=l&&tr[p].r<=r&&tr[p].sec_mx < k){
            node_update_fun(p,k-tr[p].mx,0);
            return;
        }
        push_down(p);
        int mid = (tr[p].l + tr[p].r) >> 1;
        if(r<=mid){
            range_min_fun(lc,l,r,k);
        }else if(l>mid){
            range_min_fun(rc,l,r,k);
        }else{
            range_min_fun(lc,l,mid,k);
            range_min_fun(rc,mid+1,r,k);
        }
        push_up(p);
    }
    void push_down(int p){
        int mxk = tr[p].mx_tag;
        int otherk = tr[p].other_tag;
        int mx = max(tr[lc].mx,tr[rc].mx);
        //分清楚左右儿子的值到底应该被哪个k所加
        node_update_fun(lc,tr[lc].mx==mx?mxk:otherk,otherk);
        node_update_fun(rc,tr[rc].mx==mx?mxk:otherk,otherk);
        tr[p].mx_tag = tr[p].other_tag = 0;
    }
    ll query_sum(int p,int l,int r){
        if(tr[p].l>=l&&tr[p].r<=r){
            return tr[p].sum;
        }
        push_down(p);
        int mid = (tr[p].l+tr[p].r)>>1;
        if(r<=mid){
            return query_sum(lc,l,r);
        }else if(l>mid){
            return query_sum(rc,l,r);
        }else{
            return query_sum(lc,l,mid) +
            query_sum(rc,mid+1,r);
        }
    }
    int query_max(int p,int l,int r){
        if(tr[p].l>=l&&tr[p].r<=r){
            return tr[p].mx;
        }
        push_down(p);
        int mid = (tr[p].l+tr[p].r)>>1;
        if(r<=mid){
            return query_max(lc,l,r);
        }else if(l>mid){
            return query_max(rc,l,r);
        }else{
            return max(query_max(lc,l,mid),
                       query_max(rc,mid+1,r));
        }
    
    }
    int main()
    {
        t=read();
        while(t--){
            n=read();
            m=read();
            for(int i=1;i<=n;++i) a[i] =read();
            build(1,1,n);
            int op,l,r,k;
            while(m--){
                op=read();
                l=read();
                r=read();
                if(op == 0){
                    k=read();
                    range_min_fun(1,l,r,k);
                }else if(op == 1){
                     printf("%d\n",query_max(1,l,r));
                }else{
                    printf("%lld\n",query_sum(1,l,r));
                }
            }
        }
        return 0;
    }
    
    

    例题二、

    BZOJ4695
    这题在上一题的基础之上

    • 增加了区间加
    • 区间最大值操作
    • 求区间最小值

    根据上一题区间最小值的操作 我们来仿造区间最大值操作

    对于区间最小值操作
    我们维护:区间最大值及个数、次大值
    那么对于区间最大值操作
    我们维护:区间最小值及个数、次小值
    

    那么我们就将数分为了三类:最大值、最小值、其他值
    对于题目要求的三种修改操作

    • 对于区间加(减),我们直接对这三类数加(减) 即可
    • 对于区间最小值操作以及最大值操作
      思路与例题一处相同。
      此处以区间最大值操作为例
      1.如果最大值比给定的k来得小 那么我们不需要任何操作
      2.如果这个k<最大值 但是k > 次大值
      那么我们只需要将最大值全部变成k,修改一下区间和即可.
      3.如果这个k<最大值 && k < 次大值
      那么我们当前这个结点是处理不了的,直接push_down交给儿子结点

    那么,我们需要维护三个tag

    • 最大值tag
    • 最小值tag
    • 其他值tag

    但是这里有个问题,如果一个区间内的数字很少。

    	比如只有1个或者2个
    	当只有一个数字的时候 那么最大值是等于最小值的
    	我们在push_down的时候不要搞错标记
    	
    	亦或者只有两个数字的时候 有可能发生次大值等于最小值
    	也有可能发生次小值等于最大值 
    	此时也要注意是哪个标记的作用
    

    还有一个问题,当前节点的最大最小值是从儿子节点取过来的

    此处以最大值为例
    如果儿子节点不包含最大值 
    那么我们给它加的标记应该是其他值的标记(代码中的t3)
    如果包含了 那么应该加最大值的标记(代码中的t2)
    

    Code

    #include <iostream>
    #include <cstdio>
    #define lc (p<<1)
    #define rc (p<<1|1)
    using namespace std;
    typedef long long ll;
    const int N = 550000;
    const int INF = 1e9;
    struct Node{
        int L,R;
        ll sum;
        //分别是最小值 最大值 其他值的tag
        int tag1,tag2,tag3;
        //最大值 最小值 次大值 次小值 最大值个数 最小值个数
        int fir_max,fir_min,sec_max,sec_min,mx_num,mn_num;
    }tree[N<<2];
    int a[N];
    void push_up(int p){
        tree[p].sum=tree[lc].sum+tree[rc].sum;
        if(tree[lc].fir_min==tree[rc].fir_min){
            tree[p].fir_min=tree[lc].fir_min;
            tree[p].mn_num=tree[lc].mn_num+tree[rc].mn_num;
            tree[p].sec_min=min(tree[lc].sec_min,tree[rc].sec_min);
        }else if(tree[lc].fir_min<tree[rc].fir_min){
            tree[p].fir_min=tree[lc].fir_min;
            tree[p].mn_num=tree[lc].mn_num;
            tree[p].sec_min=min(tree[lc].sec_min,tree[rc].fir_min);
        }else{
            tree[p].fir_min=tree[rc].fir_min;
            tree[p].mn_num=tree[rc].mn_num;
            tree[p].sec_min=min(tree[rc].sec_min,tree[lc].fir_min);
        }
        if(tree[lc].fir_max==tree[rc].fir_max){
            tree[p].fir_max=tree[lc].fir_max;
            tree[p].mx_num=tree[lc].mx_num+tree[rc].mx_num;
            tree[p].sec_max=max(tree[lc].sec_max,tree[rc].sec_max);
        }else if(tree[lc].fir_max>tree[rc].fir_max){
            tree[p].fir_max=tree[lc].fir_max;
            tree[p].mx_num=tree[lc].mx_num;
            tree[p].sec_max=max(tree[lc].sec_max,tree[rc].fir_max);
        }else{
            tree[p].fir_max=tree[rc].fir_max;
            tree[p].mx_num=tree[rc].mx_num;
            tree[p].sec_max=max(tree[rc].sec_max,tree[lc].fir_max);
        }
    }
    void build(int p,int l,int r){
        tree[p].L=l,tree[p].R=r;
        tree[p].tag1=tree[p].tag2=tree[p].tag3=0;
        if(l==r){
            tree[p].fir_max=tree[p].fir_min=tree[p].sum=a[l];
            tree[p].sec_max=-INF;
            tree[p].sec_min=INF;
            tree[p].mx_num=tree[p].mn_num=1;
            return;
        }
        int mid = (l+r)>>1;
        build(lc,l,mid);
        build(rc,mid+1,r);
        push_up(p);
    }
    //t1,t2,t3分别是最小值 最大值 其他值的tag标记
    void update(int p,int t1,int t2,int t3){
        //处理sum
        if(tree[p].fir_max==tree[p].fir_min){
            //如果只有一个值(最大值等于最小值)
            //那么将其他值的tag丢掉
            if(t1==t3) t1=t2;
            else if(t2==t3) t2=t1;
            tree[p].sum+=1ll*tree[p].mx_num*t2;
            //else t2=t1;
            //tree[p].sum+=1ll*t1*tree[p].mn_num;
        }
        else{
            tree[p].sum+=1ll*tree[p].mx_num*t2+1ll*tree[p].mn_num*t1+
            (tree[p].R-tree[p].L+1-tree[p].mx_num-tree[p].mn_num)*t3*1ll;
        }
        //处理次大值
        //如果次大值和最小值相等 那么给它加tag1的值
        //否则加tag3的值
        //处理次小值同理
        if(tree[p].sec_max==tree[p].fir_min){
            tree[p].sec_max+=t1;
        }else if(tree[p].sec_max!=-INF){
            tree[p].sec_max+=t3;
        }
        //处理次小值
        if(tree[p].sec_min==tree[p].fir_max){
            tree[p].sec_min+=t2;
        }else if(tree[p].sec_min!=INF){
            tree[p].sec_min+=t3;
        }
    
        //处理最大值、最小值、以及tag
        tree[p].fir_max+=t2;
        tree[p].fir_min+=t1;
        tree[p].tag1+=t1;
        tree[p].tag2+=t2;
        tree[p].tag3+=t3;
    }
    void push_down(int p){
        int mx = max(tree[lc].fir_max,tree[rc].fir_max);
        int mn = min(tree[lc].fir_min,tree[rc].fir_min);
        int l1,l2,r1,r2;
        l1=tree[lc].fir_min==mn?tree[p].tag1:tree[p].tag3;
        l2=tree[lc].fir_max==mx?tree[p].tag2:tree[p].tag3;
        update(lc,l1,l2,tree[p].tag3);
        r1=tree[rc].fir_min==mn?tree[p].tag1:tree[p].tag3;
        r2=tree[rc].fir_max==mx?tree[p].tag2:tree[p].tag3;
        update(rc,r1,r2,tree[p].tag3);
        tree[p].tag1=tree[p].tag2=tree[p].tag3=0;
    }
    
    //给一个区间[L,R] 加上一个数x
    void fun1(int p,int l,int r,int k){
        if(tree[p].L>r||tree[p].R<l) return;
        if(tree[p].L>=l&&tree[p].R<=r){
            update(p,k,k,k);
            return;
        }
        push_down(p);
        fun1(lc,l,r,k);
        fun1(rc,l,r,k);
        push_up(p);
    }
    //把一个区间[L,R] 里小于x 的数变成x
    void fun2(int p,int l,int r,int k){
         if(tree[p].L>r||tree[p].R<l||tree[p].fir_min>=k) return;
         if(tree[p].L>=l&&tree[p].R<=r&&tree[p].sec_min>k){
            update(p,k-tree[p].fir_min,0,0);
            return;
         }
        push_down(p);
        fun2(lc,l,r,k);
        fun2(rc,l,r,k);
        push_up(p);
    }
    //把一个区间[L,R] 里大于x 的数变成x
    void fun3(int p,int l,int r,int k){
        if(tree[p].L>r||tree[p].R<l||tree[p].fir_max<=k) return;
        if(tree[p].L>=l&&tree[p].R<=r&&tree[p].sec_max<k){
            update(p,0,k-tree[p].fir_max,0);
            return;
         }
        push_down(p);
        fun3(lc,l,r,k);
        fun3(rc,l,r,k);
        push_up(p);
    }
    //求区间[L,R] 的和
    ll fun4(int p,int l,int r){
         if(tree[p].L>r||tree[p].R<l) return 0;
         if(tree[p].L>=l&&tree[p].R<=r){
            return tree[p].sum;
         }
         push_down(p);
         return fun4(lc,l,r)+fun4(rc,l,r);
    }
    //求区间[L,R] 的最大值
    int fun5(int p,int l,int r){
        if(tree[p].L>r||tree[p].R<l) return -INF;
        if(tree[p].L>=l&&tree[p].R<=r){
            return tree[p].fir_max;
         }
          push_down(p);
         return max(fun5(lc,l,r),fun5(rc,l,r));
    }
    //求区间[L,R] 的最小值
    int fun6(int p,int l,int r){
        if(tree[p].L>r||tree[p].R<l) return INF;
        if(tree[p].L>=l&&tree[p].R<=r){
            return tree[p].fir_min;
         }
          push_down(p);
         return min(fun6(lc,l,r),fun6(rc,l,r));
    }
    #undef lc
    #undef rc
    int read()
    {
    	int x=0, w=0; char ch=0;
    	while (!isdigit(ch)) w|=ch=='-', ch=getchar();
    	while (isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48), ch=getchar();
    	return w?-x:x;
    }
    template<class T>
    inline void write(T x)
    {
         if(x<0) putchar('-'),x=-x;
         if(x>9) write(x/10);
         putchar(x%10+'0');//取出个位
    }
    
    int main()
    {
        int n;
        n=read();
        for(int i=1;i<=n;i++){
           a[i]=read();
        }
        build(1,1,n);
        int m;
        m=read();
        while(m--){
            int op,l,r,k;
            op=read();
            switch(op){
                case 1:
                    l=read();r=read();k=read();
                    fun1(1,l,r,k);
                    break;
                case 2:
                    l=read();r=read();k=read();
                    fun2(1,l,r,k);
                    break;
                case 3:
                    l=read();r=read();k=read();
                    fun3(1,l,r,k);
                    break;
                case 4:
                    l=read();r=read();
                    write(fun4(1,l,r));
                    putchar('\n');
                    break;
                case 5:
                     l=read();r=read();
                     write(fun5(1,l,r));
                     putchar('\n');
                    break;
                case 6:
                     l=read();r=read();
                     write(fun6(1,l,r));
                     putchar('\n');
                    break;
            }
        }
        return 0;
    }
    

    代码二

    2021.9.7复习,写了一份新的,我觉得更加适合理解,思路和上面是一致的;

    #include <iostream>
    
    using namespace std;
    
    typedef long long ll;
    
    const int N = 5e5+10;
    
    const int INF = 1e9;
    
    #define lc (p<<1)
    #define rc (p<<1|1)
    
    struct Node{
        int l,r,mx,mn,mx_num,mn_num,sec_mx,sec_mn;
        ll sum;
        int mx_tag,mn_tag,other_tag;
    }tr[N<<2];
    int n,m,a[N];
    void push_down(int p);
    
    void push_up(int p){
        Node &left = tr[lc],&right = tr[rc],&root = tr[p];
        root.sum = left.sum + right.sum;
        //操作最大值、次大值
        if(left.mx == right.mx){
            root.mx = left.mx;
            root.mx_num = left.mx_num + right.mx_num;
            root.sec_mx = max(left.sec_mx,right.sec_mx);
        }else if(left.mx > right.mx){
            root.mx = left.mx;
            root.mx_num = left.mx_num;
            root.sec_mx = max(left.sec_mx,right.mx);
        }else{
            root.mx = right.mx;
            root.mx_num = right.mx_num;
            root.sec_mx = max(right.sec_mx,left.mx);
        }
        //最小值、次小值
        if(left.mn == right.mn){
            root.mn = left.mn;
            root.mn_num = left.mn_num + right.mn_num;
            root.sec_mn = min(left.sec_mn,right.sec_mn);
        }else if(left.mn < right.mn){
            root.mn = left.mn;
            root.mn_num = left.mn_num;
            root.sec_mn = min(left.sec_mn,right.mn);
        }else{
            root.mn = right.mn;
            root.mn_num = right.mn_num;
            root.sec_mn = min(right.sec_mn,left.mn);
        }
    }
    //这个方法对某个节点的最大值、最小值、其他值加上某些数
    void node_update_fun(int p,int mnk,int mxk,int otherk){
        Node & root = tr[p];
        if(root.mx == root.mn){
            //不应该被其他值的标签所影响,因为这里只有一个值
            if(mnk == otherk) mnk = mxk;
            else mxk = mnk;
            root.sum += 1ll*root.mn_num * mnk;
        }else{
            root.sum += 1ll*root.mn_num * mnk + 1ll*root.mx_num * mxk
            + 1ll*(root.r-root.l+1-root.mn_num-root.mx_num)*otherk;
        }
        //操作次值
        if(root.mx == root.sec_mn){
            root.sec_mn += mxk;
        }else if(root.sec_mn != INF){
            root.sec_mn += otherk;
        }
        if(root.mn == root.sec_mx){
            root.sec_mx += mnk;
        }else if(root.sec_mx != -INF){
            root.sec_mx +=otherk;
        }
        root.mx += mxk;
        root.mn += mnk;
    
        root.mx_tag += mxk;
        root.mn_tag += mnk;
        root.other_tag += otherk;
    }
    void range_max_fun(int p,int l,int r,int k){
        Node &root = tr[p];
        if(root.mn >= k) return;
        if(root.l>=l&&root.r<=r&&root.sec_mn > k){
            node_update_fun(p,k-root.mn,0,0);
            return;
        }
        push_down(p);
        int mid = (root.l + root.r) >> 1;
        if(r<=mid){
            range_max_fun(lc,l,r,k);
        }else if(l>mid){
            range_max_fun(rc,l,r,k);
        }else{
            range_max_fun(lc,l,mid,k);
            range_max_fun(rc,mid+1,r,k);
        }
        push_up(p);
    }
    void range_min_fun(int p,int l,int r,int k){
        Node &root = tr[p];
        if(root.mx <= k) return;
        if(root.l>=l&&root.r<=r&&root.sec_mx<k){
            node_update_fun(p,0,k-root.mx,0);
            return;
        }
        push_down(p);
        int mid = (root.l + root.r) >> 1;
        if(r<=mid){
            range_min_fun(lc,l,r,k);
        }else if(l>mid){
            range_min_fun(rc,l,r,k);
        }else{
            range_min_fun(lc,l,mid,k);
            range_min_fun(rc,mid+1,r,k);
        }
        push_up(p);
    }
    void range_add_fun(int p,int l,int r,int k){
        Node & root = tr[p];
        if(root.l>=l&&root.r<=r){
            node_update_fun(p,k,k,k);
            return;
        }
        push_down(p);
        int mid = (root.l + root.r) >> 1;
        if(r<=mid){
            range_add_fun(lc,l,r,k);
        }else if(l>mid){
            range_add_fun(rc,l,r,k);
        }else{
            range_add_fun(lc,l,mid,k);
            range_add_fun(rc,mid+1,r,k);
        }
        push_up(p);
    }
    ll query_sum(int p,int l,int r){
        Node & root = tr[p];
        if(root.l>=l&&root.r<=r){
            return root.sum;
        }
        push_down(p);
        int mid = (root.l + root.r) >> 1;
        if(r<=mid){
            return query_sum(lc,l,r);
        }else if(l>mid){
            return query_sum(rc,l,r);
        }else{
            return query_sum(lc,l,mid)+
            query_sum(rc,mid+1,r);
        }
    }
    int query_max(int p,int l,int r){
        Node & root = tr[p];
        if(root.l>=l&&root.r<=r){
            return root.mx;
        }
        push_down(p);
        int mid = (root.l + root.r) >> 1;
        if(r<=mid){
            return query_max(lc,l,r);
        }else if(l>mid){
            return query_max(rc,l,r);
        }else{
            return max(query_max(lc,l,mid),
            query_max(rc,mid+1,r));
        }
    }
    int query_min(int p,int l,int r){
        Node & root = tr[p];
        if(root.l>=l&&root.r<=r){
            return root.mn;
        }
        push_down(p);
        int mid = (root.l + root.r) >> 1;
        if(r<=mid){
            return query_min(lc,l,r);
        }else if(l>mid){
            return query_min(rc,l,r);
        }else{
            return min(query_min(lc,l,mid),
            query_min(rc,mid+1,r));
        }
    }
    void push_down(int p){
        int mx = max(tr[lc].mx,tr[rc].mx);
        int mn = min(tr[lc].mn,tr[rc].mn);
        int mxk = tr[p].mx_tag,mnk = tr[p].mn_tag,otherk=tr[p].other_tag;
        node_update_fun(lc,tr[lc].mn==mn?mnk:otherk,
                        tr[lc].mx==mx?mxk:otherk,
                        otherk
                        );
        node_update_fun(rc,tr[rc].mn==mn?mnk:otherk,
                        tr[rc].mx==mx?mxk:otherk,
                        otherk
                        );
        tr[p].mx_tag = tr[p].mn_tag = tr[p].other_tag = 0;
    }
    
    void build(int p,int l,int r){
        tr[p].l = l,tr[p].r = r;
        tr[p].mn_tag = tr[p].mx_tag = tr[p].other_tag = 0;
        tr[p].mx = tr[p].sec_mx = -INF;
        tr[p].mn = tr[p].sec_mn = INF;
        if(l==r){
            tr[p].sum = tr[p].mn = tr[p].mx = a[l];
            tr[p].mx_num = tr[p].mn_num = 1;
            return;
        }
        int mid = (l+r) >> 1;
        build(lc,l,mid);
        build(rc,mid+1,r);
        push_up(p);
    }
    
    int main()
    {
        std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
        cin >> n;
        for(int i=1;i<=n;++i) cin >> a[i];
        build(1,1,n);
        cin >> m;
        int op,l,r,k;
        while(m--){
            cin >> op >> l >> r;
            switch(op){
                case 1:
                    cin >> k;
                    range_add_fun(1,l,r,k);
                    break;
                case 2:
                    cin >> k;
                    range_max_fun(1,l,r,k);
                    break;
                case 3:
                    cin >> k;
                    range_min_fun(1,l,r,k);
                    break;
                case 4:
                    cout << query_sum(1,l,r) <<'\n';
                    break;
                case 5:
                    cout << query_max(1,l,r) << '\n';
                    break;
                case 6:
                    cout << query_min(1,l,r) << '\n';
                    break;
            }
        }
        return 0;
    }
    
    

    例题三、

    待完成…

    展开全文
  • 区间最值问题 以Gorgeous Sequence为例: 对于线段树上每个结点,我们维护最大值,严格次大值,区间和,最大值个数即可。对于修改操作,分为三种情况讨论: 1、如果当前结点的最大值小于等于\(a\)的话,直接退出,...

    浅谈树状数组与线段树:https://www.cnblogs.com/AKMer/p/9946944.html

    区间最值问题

    Gorgeous Sequence为例:

    对于线段树上每个结点,我们维护最大值,严格次大值,区间和,最大值个数即可。对于修改操作,分为三种情况讨论:

    1、如果当前结点的最大值小于等于\(a\)的话,直接退出,因为取\(max\)操作不会对当前区间造成任何影响。

    2、如果当前结点的最大值大于\(a\)但是次大值小于等于\(a\),所以最大值都会被改成\(a\),其它值不受影响。给当前点打上一个区间与\(a\)\(min\)的标记和区间然后减去最大值个数乘以最大值与\(a\)的差值。

    3、如果当前结点的次大值大于\(a\),那么就暴力递归它的两个子树继续做。

    时间复杂度证明:

    首先第一种和第二种情况都是\(O(1)\)的,我们不用考虑。那么对于第三种情况,怎么证明时间复杂度呢?

    这个时候,吉如一线段树最重要的思想来了。

    不要试着证明每次的复杂度多么多么优秀,总复杂度总会给你一个满意的答案。

    我们记录\(fake\)为当前线段树的权值,\(fake\)记录的是所有结点的权值种数和。一开始最多是\(nlogn\)的。

    对于第三种情况,意味着当前结点的最大值和次大值都将消失不见,被\(a\)取而代之。也就是说,你递归了多少个结点,\(fake\)的权值就至少会降低多少。\(fake\)最少可以降到\(2n\)(每个结点的权值都只有一种),所以总复杂度是\(O(nlogn)\)的。

    于是乎,吉如一线段树处理这种问题的复杂度就是\(O(nlogn)\)的。

    那么假如加上加标记呢?我们考虑一下,每次区间加最后终止的结点一共会有\(logn\)个,所以这会使\(fake\)的权值增加\(mlogn\),最终复杂度还是可以接受的。

    时间复杂度:\(O((n+m)logn)\)

    空间复杂度:\(O(n)\)

    代码如下:

    #include <cstdio>
    #include <algorithm>
    using namespace std;
    typedef long long ll;
    
    const int maxn=1e6+5;
    
    int n,m;
    int a[maxn];
    
    int read() {
        int x=0,f=1;char ch=getchar();
        for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
        for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';
        return x*f;
    }
    
    struct segment_tree {
        ll sum[maxn<<2];
        int mx[maxn<<2],se[maxn<<2];
        int tag[maxn<<2],cnt[maxn<<2];
    
        void update(int p) {
            sum[p]=sum[p<<1]+sum[p<<1|1];
            mx[p]=max(mx[p<<1],mx[p<<1|1]);
            cnt[p]=(mx[p]==mx[p<<1])*cnt[p<<1];
            cnt[p]+=(mx[p]==mx[p<<1|1])*cnt[p<<1|1];
            if(mx[p]==mx[p<<1])se[p]=se[p<<1];
            else se[p]=mx[p<<1];
            if(mx[p]==mx[p<<1|1])se[p]=max(se[p],se[p<<1|1]);
            else se[p]=max(se[p],mx[p<<1|1]);
        }
    
        void build(int p,int l,int r) {
            tag[p]=-1;
            if(l==r) {
                sum[p]=mx[p]=a[l];
                se[p]=-1,cnt[p]=1;
                return;
            }
            int mid=(l+r)>>1;
            build(p<<1,l,mid);
            build(p<<1|1,mid+1,r);
            update(p);
        }
    
        void solve(int p,int limit) {
            if(mx[p]<=limit)return;
            if(se[p]<limit&&limit<mx[p]) {
                sum[p]-=1ll*(mx[p]-limit)*cnt[p];
                mx[p]=limit,tag[p]=limit;return;
            }
            solve(p<<1,limit),solve(p<<1|1,limit);
            update(p);
        }
    
        void push_down(int p) {
            if(~tag[p]) {
                solve(p<<1,tag[p]);
                solve(p<<1|1,tag[p]);
                tag[p]=-1;
            }
        }
    
        void Min(int p,int l,int r,int L,int R,int v) {
            if(L<=l&&r<=R) {solve(p,v);return;}
            int mid=(l+r)>>1;push_down(p);
            if(L<=mid)Min(p<<1,l,mid,L,R,v);
            if(R>mid)Min(p<<1|1,mid+1,r,L,R,v);
            update(p);
        }
    
        int queryMx(int p,int l,int r,int L,int R) {
            if(L<=l&&r<=R)return mx[p];
            int mid=(l+r)>>1,res=0;push_down(p);
            if(L<=mid)res=max(res,queryMx(p<<1,l,mid,L,R));
            if(R>mid)res=max(res,queryMx(p<<1|1,mid+1,r,L,R));
            return res;
        }
    
        ll querySum(int p,int l,int r,int L,int R) {
            if(L<=l&&r<=R)return sum[p];
            int mid=(l+r)>>1;ll res=0;
            push_down(p);
            if(L<=mid)res+=querySum(p<<1,l,mid,L,R);
            if(R>mid)res+=querySum(p<<1|1,mid+1,r,L,R);
            return res;
        }
    }T;
    
    int main() {
        int Test=read();
        while(Test--) {
            n=read(),m=read();
            for(int i=1;i<=n;i++)
                a[i]=read();
            T.build(1,1,n);
            for(int i=1;i<=m;i++) {
                int opt=read(),l=read(),r=read();
                if(!opt) {
                    int v=read();
                    T.Min(1,1,n,l,r,v);
                }
                if(opt==1)printf("%d\n",T.queryMx(1,1,n,l,r));
                if(opt==2)printf("%lld\n",T.querySum(1,1,n,l,r));
            }
        }
        return 0;
    }

    历史最大值

    这个东西不好讲。。。

    一般都是一个数组\(a\)一个数组\(b\)\(b_i\)记录\(a_i\)曾经到达过的最大/最小值或者是每次操作完之后\(a_i\)的和。然后在\(a\)上操作来操作去,冷不丁的问你\(b\)数组的区间最大/最小值或者是区间和。

    这种问题一般分为四类(第二类和第四类如果我碰见了果断暴力分走起)

    第一类:可以用延迟标记处理的问题

    这类问题一般用延迟标记可以解决,不过要记录标记从上一次下传标记到现在这一次的最值。维护的东西比较多,但是并不会涉及什么骚操作,对合并标记功法要求很高。

    第二类:无法用延迟标记处理的问题

    都说了不能用延迟标记处理了就弃了吧~根本不会

    第三类:无区间最值操作的区间问题

    一般都要用到辅助数组,转化成传统的问题。

    第四类:有区间最值操作的区间问题

    无区间最值操作都不会了,有区间最值还玩屁~根本不会

    参考资料:国家集训队2016论文集——吉如一《区间最值操作与历史最值问题》

    竞赛是灵活的,所以我觉得吉司机线段树要考也不会变到哪去,只要掌握这种以全局来分析问题复杂度的思想,就没问题了。这就是我不学历史最值问题的理由

    转载于:https://www.cnblogs.com/AKMer/p/10225100.html

    展开全文
  • 题目链接 题解: #include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<string> #include<vector> #include<...#incl...

    题目链接
    在这里插入图片描述
    在这里插入图片描述

    题解:

    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<cstring>
    #include<string>
    #include<vector>
    #include<map>
    #include<set>
    #include<cmath>
    #include<queue>
    #define ll long long
    #define pr make_pair
    #define pb push_back
    #define lc (cnt<<1)
    #define rc (cnt<<1|1)
    using namespace std;
    const int inf=0x3f3f3f3f;
    const ll lnf=0x3f3f3f3f3f3f3f3f;
    const double dnf=1e15;
    const int mod=1e9+7;
    const double eps=1e-8;
    const int maxn=500100;
    
    struct node
    {
        int l,r;
        int maxx,maxl,se,cnt;
        int addmaxx,addmaxl,addse,addsel;
        ll sum;
    }t[maxn<<2];
    
    int a[maxn];
    
    void pushup(int cnt)
    {
        t[cnt].maxx=max(t[lc].maxx,t[rc].maxx);
        t[cnt].maxl=max(t[lc].maxl,t[rc].maxl);
        t[cnt].sum=t[lc].sum+t[rc].sum;
    
        if(t[lc].maxx==t[rc].maxx)
        {
            t[cnt].cnt=t[lc].cnt+t[rc].cnt;
            t[cnt].se=max(t[lc].se,t[rc].se);
        }
        else if(t[lc].maxx>t[rc].maxx)
        {
            t[cnt].cnt=t[lc].cnt;
            t[cnt].se=max(t[lc].se,t[rc].maxx);
        }
        else
        {
            t[cnt].cnt=t[rc].cnt;
            t[cnt].se=max(t[lc].maxx,t[rc].se);
        }
    }
    
    void update(int cnt,int addmaxx,int addmaxl,int addse,int addsel)
    {
        t[cnt].sum+=1ll*addmaxx*t[cnt].cnt+1ll*addse*(t[cnt].r-t[cnt].l+1-t[cnt].cnt);
        t[cnt].maxl=max(t[cnt].maxl,t[cnt].maxx+addmaxl);
        t[cnt].addmaxl=max(t[cnt].addmaxl,t[cnt].addmaxx+addmaxl);
        t[cnt].maxx+=addmaxx;
        t[cnt].addmaxx+=addmaxx;
        t[cnt].addsel=max(t[cnt].addsel,t[cnt].addse+addsel);
        if(t[cnt].se!=-inf) t[cnt].se+=addse;
        t[cnt].addse+=addse;
    }
    
    void pushdown(int cnt)
    {
        int nowmaxx=max(t[lc].maxx,t[rc].maxx);
    
        if(t[lc].maxx==nowmaxx) update(lc,t[cnt].addmaxx,t[cnt].addmaxl,t[cnt].addse,t[cnt].addsel);
        else update(lc,t[cnt].addse,t[cnt].addsel,t[cnt].addse,t[cnt].addsel);
    
        if(t[rc].maxx==nowmaxx) update(rc,t[cnt].addmaxx,t[cnt].addmaxl,t[cnt].addse,t[cnt].addsel);
        else update(rc,t[cnt].addse,t[cnt].addsel,t[cnt].addse,t[cnt].addsel);
    
        t[cnt].addmaxx=t[cnt].addmaxl=t[cnt].addse=t[cnt].addsel=0;
    }
    
    void build(int l,int r,int cnt)
    {
        t[cnt].l=l,t[cnt].r=r;
        t[cnt].sum=t[cnt].maxx=t[cnt].maxl=t[cnt].se=t[cnt].cnt=0;
        t[cnt].addmaxx=t[cnt].addmaxl=t[cnt].addse=t[cnt].addsel=0;
        if(l==r)
        {
            t[cnt].sum=t[cnt].maxx=t[cnt].maxl=a[l];
            t[cnt].se=-inf,t[cnt].cnt=1;
            return ;
        }
        int mid=(l+r)>>1;
        build(l,mid,lc);
        build(mid+1,r,rc);
        pushup(cnt);
    }
    
    void change1(int l,int r,int cnt,int k)
    {
        if(l<=t[cnt].l&&t[cnt].r<=r)
        {
            update(cnt,k,k,k,k);
            return ;
        }
        pushdown(cnt);
        if(l<=t[lc].r) change1(l,r,lc,k);
        if(r>=t[rc].l) change1(l,r,rc,k);
        pushup(cnt);
    }
    
    void change2(int l,int r,int cnt,int v)
    {
        if(v>=t[cnt].maxx) return ;
        if(l<=t[cnt].l&&t[cnt].r<=r&&v>t[cnt].se)
        {
            update(cnt,v-t[cnt].maxx,v-t[cnt].maxx,0,0);
            return ;
        }
        pushdown(cnt);
        if(l<=t[lc].r) change2(l,r,lc,v);
        if(r>=t[rc].l) change2(l,r,rc,v);
        pushup(cnt);
    }
    
    ll ask3(int l,int r,int cnt)
    {
        if(l<=t[cnt].l&&t[cnt].r<=r)
            return t[cnt].sum;
        pushdown(cnt);
        ll ans=0;
        if(l<=t[lc].r) ans+=ask3(l,r,lc);
        if(r>=t[rc].l) ans+=ask3(l,r,rc);
        return ans;
    }
    
    int ask4(int l,int r,int cnt)
    {
        if(l<=t[cnt].l&&t[cnt].r<=r)
            return t[cnt].maxx;
        pushdown(cnt);
        int maxx=-inf;
        if(l<=t[lc].r) maxx=max(maxx,ask4(l,r,lc));
        if(r>=t[rc].l) maxx=max(maxx,ask4(l,r,rc));
        return maxx;
    }
    
    int ask5(int l,int r,int cnt)
    {
        if(l<=t[cnt].l&&t[cnt].r<=r)
            return t[cnt].maxl;
        pushdown(cnt);
        int maxx=-inf;
        if(l<=t[lc].r) maxx=max(maxx,ask5(l,r,lc));
        if(r>=t[rc].l) maxx=max(maxx,ask5(l,r,rc));
        return maxx;
    }
    
    int main(void)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        build(1,n,1);
    
        int op,l,r,k,v;
        for(int i=1;i<=m;i++)
        {
            scanf("%d",&op);
            if(op==1)
            {
                scanf("%d%d%d",&l,&r,&k);
                change1(l,r,1,k);
            }
            else if(op==2)
            {
                scanf("%d%d%d",&l,&r,&v);
                change2(l,r,1,v);
            }
            else if(op==3)
            {
                scanf("%d%d",&l,&r);
                printf("%lld\n",ask3(l,r,1));
            }
            else if(op==4)
            {
                scanf("%d%d",&l,&r);
                printf("%d\n",ask4(l,r,1));
            }
            else if(op==5)
            {
                scanf("%d%d",&l,&r);
                printf("%d\n",ask5(l,r,1));
            }
        }
        return 0;
    }
    
    
    展开全文
  • 对于每个节点,我们维护:当前最大值,当前次大值,历史最大值,历史次大值(这道题好像不用用到这个),当前最大值的个数,区间和,和四个懒标记 四个懒标记分别为: lazy1:当前最大值要加上的值 lazy2:历史最大...

    >Link

    luogu P6242


    >Description

    在这里插入图片描述


    >解题思路

    这个大佬写的好好%%

    对于每个节点,我们维护:当前最大值,当前次大值,历史最大值,历史次大值(这道题好像不用用到这个),当前最大值的个数,区间和,和四个懒标记

    四个懒标记分别为:

    1. lazy1:当前最大值要加上的值
    2. lazy2:历史最大值要加上的值
    3. lazy3:当前非最大值要加上的值
    4. lazy4:历史非最大值要加上的值

    加操作:全部都加上
    取min操作:考虑要取的min值 v a l val val的不同情况。 v a l val val值大于等于当前区间的最大值,不用更新; v a l val val小于最大值,且大于等于次大值,那我们就只用更新最大值的那几个数为 v a l val val,设最大值 m a x a maxa maxa的个数为 c n t cnt cnt,区间和就减去 c n t ∗ ( m a x a − v a l ) cnt*(maxa-val) cnt(maxaval);否则就继续递归下去
    剩下的操作就是常规的线段树操作

    具体操作看代码吧QAQ


    >代码

    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #define N 500010
    #define LL long long
    #define inf 1000000000
    #define l1(k) t[k].lazy1
    #define l2(k) t[k].lazy2
    #define l3(k) t[k].lazy3
    #define l4(k) t[k].lazy4
    #define ma(k) t[k].maxa
    #define p(k) t[k].pre
    #define mb(k) t[k].maxb
    #define cnt(k) t[k].cnt
    #define l(k) t[k].l
    #define r(k) t[k].r
    #define sum(k) t[k].sum
    using namespace std;
    
    struct tree
    {
    	LL l, r, maxa, pre, maxb, cnt;
    	LL lazy1, lazy2, lazy3, lazy4;
    	LL sum;
    } t[N * 10]; 
    int n, m;
    LL a[N];
    
    int read ()
    {
    	int ret = 0;
    	char cc = getchar(), zf = ' ';
    	while (cc < '0' || cc > '9') zf = cc, cc = getchar();
    	while (cc >= '0' && cc <= '9')
    	{
    		ret = ret * 10 + cc - '0';
    		cc = getchar();
    	}
    	if (zf == '-') return -ret;
    	return ret;
    }
    void pushup (int k) //把儿子的信息转移更新到第k个
    {
    	int y = k * 2;
    	sum(k) = sum(y) + sum(y + 1);
    	ma(k) = max (ma(y), ma(y + 1));
    	mb(k) = max (mb(y), mb(y + 1));
    	if (ma(y) == ma(y + 1)) //两边区间最大值相同
    	  cnt(k) = cnt(y) + cnt(y + 1), p(k) = max (p(y), p(y + 1));
    	else if (ma(y) > ma(y + 1))
    	  cnt(k) = cnt(y), p(k) = max (ma(y + 1), p(y));
    	else
    	  cnt(k) = cnt(y + 1), p(k) = max (ma(y), p(y + 1));
    }
    void build (int k, int l, int r)
    {
    	l(k) = l, r(k) = r;
    	l1(k) = l2(k) = l3(k) = l4(k) = 0;
    	if (l == r)
    	{
    		sum(k) = ma(k) = mb(k) = a[l];
    		cnt(k) = 1, p(k) = -inf;
    		return;
    	} //赋初值
    	int mid = (l + r) / 2;
    	build (k * 2, l, mid);
    	build (k * 2 + 1, mid + 1, r);
    	pushup (k);
    }
    void update (int k, int l1, int l2, int l3, int l4)
    {
    	sum(k) += (LL)(cnt(k) * l1 + (r(k) - l(k) + 1 - cnt(k)) * l3); 
    	mb(k) = max (mb(k), ma(k) + l2); //因为要考虑操作的顺序,最大的那就是之前全部操作完最大的值加上新的这段时间的历史最大值
    	ma(k) += l1;
    	if (p(k) != -inf) p(k) += l3;
    	l2(k) = max (l2(k), l1(k) + l2); //同上
    	l4(k) = max (l4(k), l3(k) + l4);
    	l1(k) += l1, l3(k) += l3;
    }
    void pushdown (int k)
    {
    	if (!l1(k) && !l2(k) && !l3(k) && !l4(k)) return;
    	int y = k * 2, maxn = max (ma(y), ma(y + 1));
    	if (ma(y) == maxn)
    	  update (y, l1(k), l2(k), l3(k), l4(k));
    	else update (y, l3(k), l4(k), l3(k), l4(k));
    	if (ma(y + 1) == maxn)
    	  update (y + 1, l1(k), l2(k), l3(k), l4(k));
    	else update (y + 1, l3(k), l4(k), l3(k), l4(k)); //分最大值是否在区间内两种情况进行处理(不在的话都看作非最大值处理
    	l1(k) = l2(k) = l3(k) = l4(k) = 0;
    }
    void add (int k, int ll, int rr, LL val)
    {
    	pushdown (k);
    	if (ll <= l(k) && r(k) <= rr)
    	{
    		update (k, val, val, val, val); //全加上
    		return;
    	}
    	int mid = (l(k) + r(k)) / 2;
    	if (ll <= mid) add (k * 2, ll, rr, val);
    	if (mid + 1 <= rr) add (k * 2 + 1, ll, rr, val);
    	pushup (k);
    }
    void newmin (int k, int ll, int rr, LL val)
    {
    	pushdown (k);
    	if (ma(k) <= val) return;
    	if (ll <= l(k) && r(k) <= rr && p(k) <= val)
    	{
    		update (k, val - ma(k), val - ma(k), 0, 0);
    		return;
    	}
    	int mid = (l(k) + r(k)) / 2;
    	if (ll <= mid) newmin (k * 2, ll, rr, val);
    	if (mid + 1 <= rr) newmin (k * 2 + 1, ll, rr, val);
    	pushup (k);
    }
    LL asksum (int k, int ll, int rr)
    {
    	pushdown (k);
    	if (ll <= l(k) && r(k) <= rr) return sum(k);
    	LL ret = 0; int mid = (l(k) + r(k)) / 2;
    	if (ll <= mid) ret += asksum (k * 2, ll, rr);
    	if (mid + 1 <= rr) ret += asksum (k * 2 + 1, ll, rr);
    	pushup (k);
    	return ret;
    }
    LL askma (int k, int ll, int rr)
    {
    	pushdown (k);
    	if (ll <= l(k) && r(k) <= rr) return ma(k);
    	int mid = (l(k) + r(k)) / 2;
    	LL ret = -inf;
    	if (ll <= mid) ret = max (ret, askma (k * 2, ll, rr));
    	if (mid + 1 <= rr) ret = max (ret, askma (k * 2 + 1, ll, rr));
    	pushup (k);
    	return ret;
    }
    LL askmb (int k, int ll, int rr)
    {
    	pushdown (k);
    	if (ll <= l(k) && r(k) <= rr) return mb(k);
    	int mid = (l(k) + r(k)) / 2;
    	LL ret = -inf;
    	if (ll <= mid) ret = max (ret, askmb (k * 2, ll, rr));
    	if (mid + 1 <= rr) ret = max (ret, askmb (k * 2 + 1, ll, rr));
    	return ret;
    }
    
    int main()
    {
    	for (int i = 0; i < N * 10; i++) ma(i) = mb(i) = p(i) = -inf;
    	n = read(), m = read();
    	for (int i = 1; i <= n; i++) a[i] = read();
    	build (1, 1, n);
    	int type, l, r, x;
    	for (int i = 1; i <= m; i++)
    	{
    		type = read(), l = read(), r = read();
    		if (type == 1) x = read(), add (1, l, r, x);
    		else if (type == 2) x = read(), newmin (1, l, r, x);
    		else if (type == 3) printf ("%lld\n", asksum (1, l, r));
    		else if (type == 4) printf ("%lld\n", askma (1, l, r));
    		else printf ("%lld\n", askmb (1, l, r));
    	}
    	return 0;
    }
    
    展开全文
  • 接下来我们开始介绍区间历史最值问题! 区间历史最值 对于一个序列 AAA,它的历史最值指的是它从初始化到当前达到的最大值 / 最小值,我们称之为历史最大值和历史最小值。维护历史最大值和历史最小值是有一些套路的...
  • Beats 的维护区间取最值操作的问题,以及维护区间历史最值的方法。本文参考自许多博客,以及吉老师 201620162016 年的集训队论文,会加上很多例题进行讲解QAQ。 区间最值操作 例题一 [HDU5306] Gorgeous Sequence ...
  • 正如其名,「历史最值线段树」记录的是区间内的历史最值。 HistoricalMaxVal == max(Tree[i].val)? 听上去是不是很简单啊?是不是我们每次记录一下max就好了啊? 好吧不讲这个正常人不会认可的想法了。 记录...
  • 区间最值mx,区间加标记add,区间覆盖标记cov,区间历史最值hmx,区间历史最大加标记hadd,区间历史最大覆盖标记hcov。注意我们在pushdown的时候要先处理子节点的历史值,因为在更新子节点的历史值时,我们还需要子...
  • 国家集训队2016论文集

    2018-02-20 16:59:10
    6 区间最值操作与历史最值问题 吉如一 杭州学军中学 99 7 再探快速傅里叶变换 毛啸 雅礼中学 123 8 从 Unknown 谈一类支持末尾插入删除的区间信息维护方法 罗哲正 安徽师范大学附属中学 141 9 小 C 的后缀数组命题...
  • 由于本题是单点查询,因此可以只考虑标记对原值的影响,不需要维护区间最值及区间历史最值。 时间复杂度 $O(m\log n)$  #include #include #define N 500010 #define lson l , mid , x #define rson mid +...
  • 线段树的区间修改加查询区间最大值相信大家都熟悉了,但是,如何查询一个历史的最大值呢? 此模板单纯是自己写写的,在oj上没有找到,是bzoj3064的弱化版,那题还有一个区间赋值的操作,更加麻烦。 #include <...
  • 题意:维护一列数,支持: 1.区间加A 2.区间减A,减法结束后每个...5.询问单点历史最值线段树lazytag维护历史最值,要记录四个数组,注意转移以及初始条件。#include #include #include #include using namespace s
  • 有一个长为n的序列Ai,要求支持查询[l,r]的最值、历史最值区间加/重设 \(Solution\) 线段树,每个点再维护一个历史(从0到现在)最大值、历史(从上次下传标记到现在)最大的set,add标记 PushDown时肯定是先下放历史...
  • 令标记为表示对这个区间加p后和c取max 再多来两个标记记录两次修改间这个节点所能得到的最大标记是多少 诶写线段树之前真应该把标记加法和节点加法先在草稿纸上写好以后再开始敲 不然写起来很难受 #include #...
  • 2.查询区间历史最大值;3.区间加;4.区间赋值。 输入 第一行一个正整数T,表示Bob需要监视CPU的总时间。然后第二行给出T个数表示在你的监视程序执行之前,Bob干的事让CPU在这段时间内每个时刻的使用率达已经达到了...
  • Tyvj 1518 CPU监控(线段树,历史最值) Solution 我们考虑用线段树维护此题。 先不考虑历史最值。 大概需要维护一种特殊的懒标记(x,y)(x,y)(x,y)表示让区间内所有数ppp,p=max(p+x,y)p=max(p+x,y)p=max(p+x,y)。 ...
  • inline void cad(int x,ll d,ll hd){ //区间加、历史最大区间加覆盖 if(fz[x]>-INF) //如果有赋值标记 hfz[x]=max(hfz[x],fz[x]+hd), //更新历史最大赋值 fz[x]+=d; //合并到赋值标记 else...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 527
精华内容 210
关键字:

区间历史最值