小翔和泰拉瑞亚（线段树+思维）

我会带着你远行 2023-07-06 11:40 2阅读 0赞

链接：[https://ac.nowcoder.com/acm/contest/3566/D][https_ac.nowcoder.com_acm_contest_3566_D]  
来源：牛客网

--------------------

# 小翔和泰拉瑞亚 #

时间限制：C/C++ 1秒，其他语言2秒
    空间限制：C/C++ 131072K，其他语言262144K
    64bit IO Format: %lld

## 题目描述 ##

小翔爱玩泰拉瑞亚 。  
一天，他碰到了一幅地图。这幅地图可以分为n列，第i列的高度为Hi，他认为这个地图不好看，决定对它进行改造。  
小翔又学会了m个魔法，实施第i个魔法可以使地图的第Li列到第Ri列每一列的高度减少Wi，每个魔法只能实施一次，魔法的区间可能相交或包含。  
小翔认为，一幅地图中最高的一列与最低的一列的高度差越大，这幅地图就越美观。  
小翔可以选择m个魔法中的任意一些魔法来实施，使得地图尽量美观。但是他不知道该如何选择魔法，于是他找到了你。请你求出所有可行方案中，高度差的最大值。  
对于100%的数据，满足1≤n,m≤200000,-109≤Hi≤109,1≤Wi≤109,1≤Li≤Ri≤n。

## 输入描述: ##

输入文件的第一行包含两个整数n,m。  
输入的第二行包含n个整数，相邻两数间用一个空格隔开，第i个整数为Hi。  
接下来的m行，每行包含3个整数，分别是Li,Ri,Wi，相邻两数间用一个空格隔开。

## 输出描述: ##

一行一个整数，表示高度差的最大值。

## 示例1 ##

输入  
复制

3 3
    7 -2 -10
    1 3 4
    3 3 4
    1 2 8

输出  
复制

## 思路： ##

区间更新，线段树去维护。  
极差最大，值只减小，考虑固定最小值，然后求整个区间的最大值。  
假设`i`位置上的值是最小值，那么覆盖了i的区间都可以对i位置上的值变小产生贡献，即`[l,r],l<=i&&r>=i`的区间能够让假设位置的最小值变小（`l<i&&r>=i`的在`i`之前已经使用了但是没有被撤销，此时只需使用`l=i`的区间）。那么此时应该把这些区间都使用一下，然后询问一下整个区间的最大值。  
按上述假设做的正确性很容易证明：如果最大值在使用过的区间里面，因为是同时更新，对结果没有影响；如果不在使用的区间里面，那更明显，最小值变小了，最大值没有受到影响，极差肯定变大！  
此时要考虑`i+1`为最小值了，之前用过的区间对`i+1`位置没有贡献的要撤销，因为可能影响到最大值。之前使用的区间`[l,r]`对`i+1`没有贡献的条件是：`r<i+1`。即在每次使用`i+1`之前把`r=i`的区间撤销。  
时间复杂度分析：  
影响时间复杂度的是区间操作（不能单纯看循环来定时间复杂度）。  
对于区间操作，每个区间最多操作2次，每次操作复杂度为logn,  
共m个区间，所以时间复杂度为：**mlogn**

## AC代码: ##

#include <bits/stdc++.h>
    #define lson rt<<1,l,mid
    #define rson rt<<1|1,mid+1,r
    #define ls rt<<1
    #define rs rt<<1|1
    using namespace std;
    typedef long long LL;
    const LL N = 2e5+5;
    const LL INF = 0x3f3f3f3f3f3f3f3f;
    int a[N];
    struct Node
    {
        
        LL minx,maxx;
        LL tag;
    }node[N<<2];
    struct PII
    {
        
       int l,r,v;
    };
    vector<PII> L[N],R[N];
    inline void push_up(int rt)
    {
        
        node[rt].minx = min(node[ls].minx,node[rs].minx);
        node[rt].maxx = max(node[ls].maxx,node[rs].maxx);
        return;
    }
    void build_tree(int rt,int l,int r)
    {
        
        node[rt].tag = 0;
        if(l == r)
        {
        
            node[rt].minx = a[l];
            node[rt].maxx = a[l];
            return;
        }
        int mid = (l + r) >> 1;
        build_tree(lson);
        build_tree(rson);
        push_up(rt);
    }
    inline void push_down(int rt)
    {
        
        if(node[rt].tag)
        {
        
            //认真思考，不要少更新了需要维护的值！
            node[ls].minx += node[rt].tag;
            node[ls].maxx += node[rt].tag;
            node[ls].tag += node[rt].tag;
            node[rs].minx += node[rt].tag;
            node[rs].maxx += node[rt].tag;
            node[rs].tag += node[rt].tag;
            node[rt].tag = 0;
        }
        return;
    }
    void update_range(int L,int R,int v,int rt,int l,int r)
    {
        
        if(L <= l && r <= R)
        {
        
            node[rt].minx += v;
            node[rt].maxx += v;
            node[rt].tag += v;
            return;
        }
        push_down(rt);
        int mid = (l + r) >> 1;
        if(L <= mid)
            update_range(L,R,v,lson);
        if(R > mid)
            update_range(L,R,v,rson);
        push_up(rt);
    }
    int main()
    {
        
        int n,m;
        scanf("%d%d",&n,&m);
        for(int i = 1; i <= n; i++)
        {
        
            scanf("%d",&a[i]);
        }
        build_tree(1,1,n);
        PII p;
        while(m--)
        {
        
            scanf("%d%d%d",&p.l,&p.r,&p.v);
            L[p.l].push_back(p);
            R[p.r].push_back(p);
        }
        LL ans = node[1].maxx - node[1].minx;
        for(int i = 1; i <= n; i++)
        {
        
            int lSize = L[i].size();
            int rSize = R[i].size();
            for(int j = 0; j < lSize; j++)
            {
        
                update_range(L[i][j].l,L[i][j].r,-L[i][j].v,1,1,n);
            }
            ans = max(ans,node[1].maxx - node[1].minx);
            for(int j = 0; j < rSize; j++)
            {
        
                update_range(R[i][j].l,R[i][j].r,R[i][j].v,1,1,n);
            }
        }
        printf("%lld\n",ans);
        return 0;
    }

**另一种写法：**

#include <bits/stdc++.h>
    #define lson rt<<1,l,mid
    #define rson rt<<1|1,mid+1,r
    #define ls rt<<1
    #define rs rt<<1|1
    using namespace std;
    typedef long long LL;
    const LL N = 2e5+5;
    const LL INF = 1e18;
    int a[N];
    struct Node
    {
        
        LL minx,maxx;
        LL tag;
    }node[N<<2];
    struct PII
    {
        
       int l,r,v;
    };
    vector<PII> L[N],R[N];
    inline void push_up(int rt)
    {
        
        node[rt].minx = min(node[ls].minx,node[rs].minx);
        node[rt].maxx = max(node[ls].maxx,node[rs].maxx);
    }
    void build(int rt,int l,int r)
    {
        
        node[rt].tag = 0;
        if(l == r)
        {
        
            node[rt].minx = a[l];
            node[rt].maxx = a[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(lson);
        build(rson);
        push_up(rt);
    }
    inline void push_down(int rt)
    {
        
        if(node[rt].tag)
        {
        
            node[ls].minx += node[rt].tag;
            node[ls].maxx += node[rt].tag;
            node[ls].tag += node[rt].tag;
            node[rs].minx += node[rt].tag;
            node[rs].maxx += node[rt].tag;
            node[rs].tag += node[rt].tag;
            node[rt].tag = 0;
        }
        return;
    }
    void update_range(int L,int R,int v,int rt,int l,int r)
    {
        
        if(L <= l && r <= R)
        {
        
            node[rt].minx += v;
            node[rt].maxx += v;
            node[rt].tag += v;
            return;
        }
        push_down(rt);
        int mid = (l + r) >> 1;
        if(L <= mid)
            update_range(L,R,v,lson);
        if(R > mid)
            update_range(L,R,v,rson);
        push_up(rt);
    }
      
    LL query_min(int L,int R,int rt,int l,int r)
    {
        
        if(L <= l && r <= R)
        {
        
            return node[rt].minx;
        }
        push_down(rt);
        int mid = (l + r) >> 1;
        LL res = INF;
        if(L <= mid)
            return min(res,query_min(L,R,lson));
        if(R > mid)
            return min(res,query_min(L,R,rson));
       return res;
    }
    LL query_max(int L,int R,int rt,int l,int r)
    {
        
        if(L <= l && r <= R)
        {
        
            return node[rt].maxx;
        }
        push_down(rt);
        int mid = (l + r) >> 1;
        LL res = -INF;
        if(L <= mid)
            return max(res,query_max(L,R,lson));
        if(R > mid)
            return max(res,query_max(L,R,rson));
       return res;
    }
    int main()
    {
        
        int n,m;
        scanf("%d%d",&n,&m);
        for(int i = 1; i <= n; i++)
        {
        
            scanf("%d",&a[i]);
        }
        build(1,1,n);
        PII p;
        while(m--)
        {
        
            scanf("%d%d%d",&p.l,&p.r,&p.v);
            L[p.l].push_back(p);
            R[p.r].push_back(p);
        }
        LL ans = -INF;
        for(int i = 1; i <= n; i++)
        {
        
            int lSize = L[i].size();
            int rSize = R[i].size();
            for(int j = 0; j < lSize; j++)
            {
        
                update_range(L[i][j].l,L[i][j].r,-L[i][j].v,1,1,n);
            }
            /*
            这里去query_max(1,n,1,1,n)会测试样例的5%会时间超限，
            因为update_range的时候，更新结果会push_up上去,
            此时完全可以不写query（我写是因为很久没写了，巩固一下），
            node[1]上的最值即为需要的值。
            */
            ans = max(ans,node[1].maxx-query_min(i,i,1,1,n));
            for(int j = 0; j < rSize; j++)
            {
        
                update_range(R[i][j].l,R[i][j].r,R[i][j].v,1,1,n);
            }
      
        }
        printf("%lld\n",ans);
        return 0;
    }

[https_ac.nowcoder.com_acm_contest_3566_D]: https://ac.nowcoder.com/acm/contest/3566/D