嘘~ 正在从服务器偷取页面 . . .

CF1406D Three Sequences 题解

发布日期: 2024-03-20

更新日期: 2024-03-20

文章字数: 744

CF1406D Three Sequences 题解

题意：

给定一个序列$a_1,a_2,\ldots ,a_n$，长度为 $n$ 的序列 $b,c$ 符合以下条件

$a_i=b_i+c_i$

$b$ 为不下降序列，$c$ 为不上升序列，即 $b_i\geq b_{i-1}, c_i\leq c_{i-1}$

有 $q$ 个操作，每次操作可以把 $[l,r]$ 的数增加 $x$。求每次操作后最小的 $\max(b_i,c_i)$ 。

输入格式：

第一行包含一个整数 $n$（$1\leq n\leq 10^5$）。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$1\leq i\leq n$，$-10^9\leq a_i\leq 10^9$）。

第三行包含一个整数 $q$（$1\leq q\leq 10^5$）。

接下来的每行（共 $q$ 行）包含三个整数 $l,r,x$（$1\leq l\leq r\leq n, -10^9\leq x\leq 10^9$），描述了下一次的操作。

输出格式：

输出 $q+1$ 行。

在第 $i$ 行（$1 \leq i \leq q+1$），打印经过 $i-1$ 次变化后序列的问题答案。

容易发现以下两个性质

对于序列中的升序，一定由 $c_i$ 来实现，$b_i$ 保持全相等；降序则由 $b_i$ 实现， $c_i$ 保持全相等。
$b_i$ 中的最大值为 $b_n$ ，$c_i$ 中的最大值为 $c_1$ ，则 $\max \left\{b_n, c_1\right\}=\left\lceil\frac{b_n+c_1}{2}\right\rceil$

由性质2亦可知

$\left\lceil\frac{b_n+c_1}{2}\right\rceil=\left\lceil\frac{\left(b_1+c_1\right)+\sum_{i=2}^n (b_i-b_{i-1})}{2}\right\rceil$

因为 $b_1+c_1=a_1$ ，记 $d_i = b_i - b_{i-1}$ ，则 $d_i = \left(a_i-a_{i-1}\right) \times\left[a_i \geq a_{i-1}\right]$ ，这可以预处理出来。

于是我们对于没有修改的情况已经得到答案了，而修改是区间加法使得我们可以用树状数组轻松维护。

时间复杂度 $\mathcal{O}(q \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 N ((int)(1e5 + 15))

int n, q, a[N], d[N], tr[N];
int lowbit(int x) { return x & (-x); }
void add(int x, int v) { for(int i = x; i && i <= n; i += lowbit(i)) tr[i] += v; }
int sum(int x, int r = 0) { for(int i = x; i; i -= lowbit(i)) r += tr[i]; return 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; int S = 0;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 2; i <= n; i++) d[i] = (a[i] - a[i - 1]) * (a[i] >= a[i - 1]);
    for(int i = 2; i <= n; i++) S += d[i];
    cout << (int)ceil((a[1] + S) * 1.0 / 2) << '\n';
    cin >> q;
    for(int l, r, v; q--; )
    {
        cin >> l >> r >> v; add(l, v); add(r + 1, -v);
        int x = a[l - 1] + sum(l - 1), y = a[l] + sum(l);
        if(l > 1) { S -= d[l]; d[l] = (y - x) * (y >= x); S += d[l]; }
        x = a[r] + sum(r), y = a[r + 1] + sum(r + 1);
        if(r < n) { S -= d[r + 1]; d[r + 1] = (y - x) * (y >= x); S += d[r + 1]; }
        cout << (int)ceil((a[1] + sum(1) + S) * 1.0 / 2) << '\n';
    }
    return 0;
}