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;
}