CF739C Alyona and towers 题解

题意：

现在有 \(n\) 个数，\(m\) 个操作，每次区间加一个数，对于每一次操作，你要找出最长的 \(a_l,\cdots, a_r\)，满足

\[ \exists k\! \in\![l,r],a_l<a_{l+1}<a_{l+2}<\cdots <a_k > a_{k+1}>a_{k+2}>...>a_r \] 输出其长度。（注意 \(k=l\) 也是可以的）

输入格式：

第一行一个整数 \(n\)，表示数的个数。

第二行 \(n\) 个整数 \(a_i\)。

第三行一个整数 \(m\)，表示操作个数。

下面 \(m\) 行，每行 \(3\) 个整数，\(l_i,r_i,d_i\)，表示将 \(l_i\) 到 \(r_i\) 的数字加 \(d_i\)。

输出格式：

对于每个操作，输出操作完后的答案（见题意）。

数据范围：

\(1 \le n,m \le 3\times 10^5,~ 1\le a_i \le 10^9\) 。

考虑对原数组进行差分，区间修改就变成了单点修改

此时一个正常的 /\ 型区间就变成了一段正数加一段负数

线段树上每个维护 ans 、 pre 、suf 分别表示答案、左端点为开头的答案和右端点为开头的答案

因为是单点修改甚至不需要 push down ，很方便。

时间复杂度 \(\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 N ((int)(3e5 + 15))
#define ls(at) ((at) << 1)
#define rs(at) ((at) << 1 | 1)
#define sgn(x) (((x) > 0) - ((x) < 0))

int n, Q, a[N], b[N];
struct node { int ans, pre, suf, l, r; } tr[N * 4];
void push_up(int at)
{
    auto &l = tr[ls(at)], &r = tr[rs(at)];
    up(tr[at].ans = l.ans, r.ans);
    up(tr[at].ans, max(l.pre, r.suf));
    if(!a[l.r] || !a[r.l] || sgn(a[l.r]) < sgn(a[r.l])) {
        tr[at].pre = l.pre; tr[at].suf = r.suf;
    }else {
        up(tr[at].ans, l.suf + r.pre);
        if(l.pre == l.r - l.l + 1) tr[at].pre = l.pre + r.pre;
        else tr[at].pre = l.pre;
        if(r.suf == r.r - r.l + 1) tr[at].suf = r.suf + l.suf;
        else tr[at].suf = r.suf;
    }
}
void build(int l, int r, int at)
{
    if(l == r)
    {
        if(!a[l]) tr[at] = {0, 0, 0, l, l};
        else tr[at] = {1, 1, 1, l, l};
        return;
    }
    int mid = (l + r) >> 1; tr[at].l = l; tr[at].r = r;
    build(l, mid, ls(at)); build(mid + 1, r, rs(at)); push_up(at);
}
void Modify(int x, int k, int l = 1, int r = n - 1, int at = 1)
{
    if(l == r)
    {
        a[l] += k;
        if(!a[l]) tr[at] = {0, 0, 0, l, l};
        else tr[at] = {1, 1, 1, l, l};
        return;
    }
    int mid = (l + r) >> 1;
    if(x <= mid) Modify(x, k, l, mid, ls(at));
    else Modify(x, k, mid + 1, r, rs(at));
    push_up(at);
}
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;
    for(int i = 1; i <= n; i++) cin >> b[i];
    for(int i = 1; i < n; i++) a[i] = b[i + 1] - b[i];
    if(n == 1) {
        cin >> Q; for(int i = 1; i <= n; i++) cout << "1\n"; return 0;
    }
    build(1, n - 1, 1); cin >> Q;
    for(int l, r, d; Q--; ) {
        cin >> l >> r >> d;
        if(l != 1) Modify(l - 1, d);
        if(r != n) Modify(r, -d);
        cout << tr[1].ans + 1 << '\n';
    }
    return 0;
}