CF935F Fafa and Array 题解

题意：

给出一个序列 \(a\)，定义函数 \(f(a)=\sum_{i=1}^{n-1}|a_i-a_{i+1}|\)。

给出两种操作:

\(\texttt{1 l r x}\)，表示在区间 \([l,r]\) 内找一个位置，

使得把这个位置的值加上 \(x\) 后 \(f(a)\) 最大，求这个最大值（修改是临时的）。

\(\texttt{2 l r x}\)，表示把区间 \([l,r]\) 加上 \(x\)。

输入格式

第一行一个正整数 \(n~(3 \le n \le 10^5)\) ，表示数组的长度。

第二行 \(n\) 个正整数 \(a_{1},a_{2},...,a_{n}~(0 < a_i \le 10^9)\) ，表示数组的元素。

第三行一个正整数 \(q~(1 \le q \le 10^5)\) ，表示询问的个数。

接下来 \(q\) 行，第 \(i\) 行有四个整数 \(t_i,l_i,r_i,x_i~(t_i \in\{1, 2\},\,1<l_i \leq r_i<n,\, 0<x_i \leq 10^9)\) 。

数据保证至少有一个询问。

输出格式

对于每个询问，输出一行答案。

注意到在某个 \(a_i\) 上修改造成的影响与 \(a_{i-1},a_{i+1}\) 有关，因此考察 \(a_i + x\) 与 \(a_{i-1},a_{i+1}\) 间的大小关系

若 \(a_i+x<a_{i-1}\, \land \, a_i+x<a_{i+1}\) ，则贡献为 \(\Delta = -2x\) 。
若 \(a_{i-1}<a_i+x<a_{i+1}\) ，则贡献为 \[ \begin{aligned} \Delta&=\left(\left|\left(a_i+x\right)-a_{i+1}\right|+\left|a_{i-1}-\left(a_i+x\right)\right|\right)-\left(\left|a_i-a_{i+1}\right|+\left|a_{i-1}-a_i\right|\right) \\[8pt] & =-x+\left|a_i-a_{i-1}+x\right|+\left|a_i-a_{i-1}\right| \quad\leq 0 \end{aligned} \]
若 \(a_{i-1} \leq a_i+x\,\land\, a_{i+1} \leq a_i+x\) ，
- \(a_{i-1} \leq a_i,~a_{i+1} \leq a_i\) ，那么 \(\Delta = 2x\) 。
- \(a_{i-1} \leq a_i<a_{i+1}\) ，那么 \(\Delta = 2x - 2(a_{i+1} - a_i)\) 。
- \(a_i<a_{i-1}\, \land \, a_i<a_{i+1}\) ，那么 \(\Delta = 2x - 2((a_{i-1} - a_i) + (a_{i+1} - a_i))\) 。

显然只有第三种情况贡献为正，也就是对可以让 \(f(a)\) 增大。

考虑用线段树维护 \(\max \left(0, a_{i-1}-a_i\right)+\max \left(0, a_{i+1}-a_i\right)\) 的最小值。

这个差分一下就是 \(\max \left(0,-a_{i-1}\right)+\max \left(0, a_i\right)\) 的最小值，需要特判 \(l=1\) 和 \(r=n\) 的情况。

那么贡献可能为负吗？显然当 \(l=r\) 时我们只能强行修改，特判即可。

注意线段树单点修改了 \(x\) 后 \(x+1\) 的那个最小值会变更，需要额外跑一遍修改。

时间复杂度 \(\mathcal{O}(n \log n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(1e5 + 15))
#define ls(at) ((at) << 1)
#define rs(at) ((at) << 1 | 1)

int n, ans, a[N], tr[N * 4];
void push_up(int at) { down(tr[at] = tr[ls(at)], tr[rs(at)]); }
void build(int at = 1, int l = 1, int r = n - 1)
{
    if(l == r) {
        if(l > 1) tr[at] = max(0ll, a[l]) + max(0ll, -a[l - 1]);
        ans += abs(a[l]); return;
    }
    int mid = (l + r) >> 1;
    build(ls(at), l, mid); build(rs(at), mid + 1, r); push_up(at);
}
void modify(int x, int v, int at = 1, int l = 1, int r = n - 1)
{
    if(l == r)
    {
        ans += abs(a[l] + v) - abs(a[l]), a[l] += v;
        if(x > 1) tr[at] = max(0ll, -a[l - 1]) + max(0ll, a[l]);
        if(v && x < n - 1) modify(x + 1, 0); return;
    }
    int mid = (l + r) >> 1;
    x <= mid ? modify(x, v, ls(at), l, mid) : modify(x, v, rs(at), mid + 1, r); push_up(at);
}
int qry(int nl, int nr, int at = 1, int l = 1, int r = n - 1)
{
    if(nl <= l && r <= nr) return tr[at];
    int mid = (l + r) >> 1;
    if(nl > mid) return qry(nl, nr, rs(at), mid + 1, r);
    if(nr <= mid) return qry(nl, nr, ls(at), l, mid);
    return min(qry(nl, nr, ls(at), l, mid), qry(nl, nr, rs(at), mid + 1, r));
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n; rep(i, 1, n) cin >> a[i];
    rep(i, 1, n - 1) a[i] = a[i + 1] - a[i];
    build(); int q; cin >> q;
    rep(i, 1, q)
    {
        static int op, l, r, x; cin >> op >> l >> r >> x;
        if(op == 1)
        {
            if(l == r)
            {
                if(l == 1) cout << (ans - abs(a[l]) + abs(a[l] - x)) << '\n';
                else if(l == n) cout << (ans - abs(a[l - 1]) + abs(a[l - 1] + x)) << '\n';
                else cout << (ans - abs(a[l - 1]) - abs(a[l]) + abs(a[l - 1] + x) + abs(a[l] - x)) << '\n';
            }else
            {
                int tmp = 2 * (x - qry(l > 1 ? l : 2, r));
                if(l == 1) up(tmp, -abs(a[l]) + abs(a[l] - x));
                if(r == n) up(tmp, -abs(a[r - 1]) + abs(a[r - 1] + x));
                cout << (ans + max(0ll, tmp)) << '\n';
            }
        }else { if(l > 1) modify(l - 1, x); if(r < n) modify(r, -x); }
    }
    return 0;
}