ZOJ3943 Himalayas（线段树+差分）

小灰灰 2021-12-03 05:01 231阅读 0赞

## 题意：有n座山，每座山有个高度，若满足1<i<n&&Hi-1>Hi<Hi+1，那么它就是山谷，每次地震，第L到第R座山高度会发生变化，每座山变化为A+(i-L)\*B(1<=i<=n)，问每次地震后有几座山谷。 ##

## 分析：相当于区间加一个等差数列，和洛谷P1438差不多，对原数组差分之后，考虑用线段树对差分数组进行维护，区间操作可以变为三段处理，如果我们给某一个区间 l 到 r 加上一个首相为k 公差为d 的等差序列，相当于 给 l 这个点的差分数组 加上 k，l+1 到 r 的这段数组 加上d，r+1 这个点差分数组加上 -(k+(r-l+1-1)\*d)。差分数组中如果a\[i\]<0&&a\[i+1\]>0则形成一个山谷，维护最小值和小于等于0的最大值（大于0的最小值，因为公差B>0，所以只需要考虑最小值和小于等于0的最大值，画个早图很容易理解的）以及区间两端的值，暴力更新，复杂度有点玄学。这题的数据加强了，要加个读入挂才行。现在的代码会TLE，懒得加了。 ##

## 参考：[http://www.voidcn.com/article/p-tnhliqct-mm.html][http_www.voidcn.com_article_p-tnhliqct-mm.html]、[https://blog.csdn.net/a664607530/article/details/78107759][https_blog.csdn.net_a664607530_article_details_78107759]。   代码： ##

#include<bits/stdc++.h>
    using namespace std;
    typedef long long LL;
    const int N = 1e6 + 4;
    int T, n, m, x, a[N], b[N], l, r, A, B;
    
    struct Seg
    {
        const static int N = 8e5 + 10;
        LL f[N], L[N], R[N], t[N], sum[N];
        ///f数组表示区间内山谷的个数
        ///L数组表示区间左端点的值
        ///R数组表示区间左端点的值
        ///t数组表示区间小于0的最大值或者大于0的最小值
        ///sum数组相当于lazy延迟标记
        void update(int x)
        {
            f[x] = f[x << 1] + f[x << 1 | 1] + (R[x << 1] > 0 && L[x << 1 | 1] < 0);///左端点差分值小于0右端点差分值大于0 新增一个山谷
            L[x] = L[x << 1]; R[x] = R[x << 1 | 1];///左右端点向上传递（左右都是一致的，赋值就行）
            if (max(t[x << 1], t[x << 1 | 1]) <= 0) t[x] = max(t[x << 1], t[x << 1 | 1]);///小于0的最大值
            else t[x] = min(t[x << 1], t[x << 1 | 1]);///大于0的最小值或者大于0的最小值
        }
        void build(int x, int l, int r)
        {
            f[x] = sum[x] = 0;
            if (l == r) { L[x] = R[x] = t[x] = b[l]; return; }
            int m = l + r >> 1;
            build(x << 1, l, m);
            build(x << 1 | 1, m + 1, r);
            update(x);
        }
        void pushdown(int x)///更新延迟标记
        {
            sum[x << 1] += sum[x];    sum[x << 1 | 1] += sum[x];
            L[x << 1] += sum[x];  L[x << 1 | 1] += sum[x];
            R[x << 1] += sum[x];  R[x << 1 | 1] += sum[x];
            t[x << 1] += sum[x];  t[x << 1 | 1] += sum[x];
            sum[x] = 0;
        }
        void insert(int x, int l, int r, int ll, int rr, LL c)
        {
            if (sum[x]) pushdown(x);
            if (ll <= l&&r <= rr)
            {
                if (l == r)///单点 直接更新
                {
                    L[x] += c;  R[x] += c;  t[x] += c;
                }
                else
                {
                    if (t[x] <= 0 && t[x] + c >= 0)///山谷个数有变化 继续递归更新
                    {
                        int m = l + r >> 1;
                        insert(x << 1, l, m, ll, rr, c);
                        insert(x << 1 | 1, m + 1, r, ll, rr, c);
                        update(x);
                    }
                    else///山谷个数无变化 直接返回
                    {
                        L[x] += c;  R[x] += c;  t[x] += c;  sum[x] += c;
                    }
                }
            }
            else
            {
                int m = l + r >> 1;
                if (ll <= m) insert(x << 1, l, m, ll, rr, c);
                if (rr > m) insert(x << 1 | 1, m + 1, r, ll, rr, c);
                update(x);
            }
        }
    }seg;
    
    int main()
    {
        scanf("%d", &T);
        while (T--)
        {
            scanf("%d%d", &n, &m);
            for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
            for (int i = 1; i <= n; i++) b[i] = a[i + 1] - a[i];
            if (n <= 2)///点数小于三，构不成山谷
            {
                while (m--)
                {
                    scanf("%d%d%d%d", &l, &r, &A, &B);
                    printf("0\n");
                }
                continue;
            }
            seg.build(1, 1, n - 1);
            while (m--)
            {
                scanf("%d%d%d%d", &l, &r, &A, &B);
                ///差分数组  三段处理
                if (l > 1) seg.insert(1, 1, n - 1, l - 1, l - 1, A);
                if (l < r) seg.insert(1, 1, n - 1, l, r - 1, B);
                if (r < n) seg.insert(1, 1, n - 1, r, r, -((LL)(r - l)*B + A));
                printf("%lld\n", seg.f[1]);
            }
        }
        return 0;
    }

[http_www.voidcn.com_article_p-tnhliqct-mm.html]: http://www.voidcn.com/article/p-tnhliqct-mm.html
[https_blog.csdn.net_a664607530_article_details_78107759]: https://blog.csdn.net/a664607530/article/details/78107759