CF1406D Three Sequences 题解
题目链接：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;
}参考文献：
