17.CF739C Alyona and towers 区间合并线段树

17.CF739C Alyona and towers 区间合并线段树

给定序列，要求支持区间加，以及查询最长先增后减子区间(单峰序列)长度

非常典型的区间合并线段树，记录左右起LIS，LCS，单峰

洛谷传送门：​​CF739C Alyona and towers - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)​​

CF传送门：​​Problem - 739C - Codeforces​​

题目分析

CSDN的SVG图像显示可能有点问题？

给定序列，要求支持区间加，以及查询最长先增后减子区间(单峰序列)长度。

区间和并线段树，我们需要记录每个区间的最大的左端点起长度()、左端点起长度()、右端点结束长度()、右端点结束长度()、左端点起单峰长度、右端点起单峰长度，无限制单峰长度，以及左右端点。

考虑合并的方式：对于两个区间，在合并的方式，容易想到端点的关系决定了合并后的结果：

我们首先需要对合并的结果进行初始化，我们设合并后的信息为，加号右侧信息(就是右区间)，则：

res.lv = lv, res.rv = x.rv;
res.llis = llis, res.llds = llds;
res.rlis = x.rlis, res.rlds = x.rlds;
res.plm = plm, res.prm = x.prm;
res.ans = max(ans, x.ans);
res.len = len + x.len;

1. 左区间右端点值右区间左端点值：
   因为端点大小关系，此时一定无法合并。

• 对于左端点起的合并：分两种情况：

1. 左区间左端点起长度等于左区间长度，即 左区间整个区间都是序列：
   
   +
   
   +此时只需要直接把右区间左起长度+左区间长度合并即可：

if(llis == len) res.llis += x.llis;

1. 否则不能合并，因为两个左起序列之间不严格递增：
   
   +
   
   +

• 对于右端点结束的合并，同样分两种情况：

1. 有区间右端点结束长度等于右区间长度，即 右区间整个区间都是序列：
   
   +
   
   +此时只需要直接把右区间长度+左区间右端点结束长度：

if(x.rlis == x.len) res.rlis += rlis;

1. 否则不能合并：
   
   +
   
   +

• 对于峰值位于右区间的单峰：

1. 如果右区间单峰长度等右区间长度：
   
   +
   
   +那么就可以与左区间右端点结束合并:

if(x.prm == x.len) res.prm += rlis;

1. 如果左区间长度等于左区间长度：
   
   +
   
   + Viewer does not support full SVG 1.1

if(llis == len) res.plm = max(res.plm, len + x.plm);

• 然后需要加入合并过程中损失的信息：左区间右端点结束和右区间左端点起单峰：
  
  +
  
  + Viewer does not support full SVG 1.1

res.ans = max(res.ans, rlis + x.plm);

1. 类似的，当左区间右端点值右区间左端点值时，我们对和单峰、答案采取类似的方式进行合并即可。

综上所述，我们可以得到区间合并信息的过程：

struct info{
    int lv = 0, rv = 0;
    int ans = 1, llis = 1, llds = 1, rlis = 1, rlds = 1, plm = 1, prm = 1, len = 1;
    info() {}
    info(int val): lv(val), rv(val) {}
    info operator+ (info &x) {
        info res;
        res.lv = lv, res.rv = x.rv, res.ans = max(ans, x.ans);
        res.llis = llis, res.llds = llds;
        res.rlis = x.rlis, res.rlds = x.rlds;
        res.plm = plm, res.prm = x.prm;
        res.len = len + x.len;
        if(rv < x.lv){
            if(llis == len) res.llis += x.llis;
            if(x.rlis == x.len) res.rlis += rlis;
            if(x.prm == x.len) res.prm += rlis;
            if(llis == len) res.plm = max(res.plm, len + x.plm);
            res.ans = max(res.ans, rlis + x.plm);
        }   
        else if(rv > x.lv){
            if(llds == len) res.llds += x.llds;
            if(x.rlds == x.len) res.rlds += rlds;
            if(plm == len) res.plm += x.llds;
            if(x.rlds == x.len) res.prm = max(res.prm, x.len + prm);
            res.ans = max(res.ans, prm + x.llds);
        }
        return res;
    }
}tree[N << 2];

剩下的就是线段树板子了。

Code

#include <bits/stdc++.h>
#pragma gcc optimize("O2")
#pragma g++ optimize("O2")
#define int long long
#define endl '\n'
using namespace std;

const int N = 4e5 + 10, MOD = 1e9 + 7;
int a[N];

namespace ffastIO {
    const int bufl = 1 << 15;
    char buf[bufl], *s = buf, *t = buf;
    inline int fetch() {
        if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
        return *s++;
    }
    inline int read() {
        int a = 0, b = 1, c = fetch();
        while (!isdigit(c))b ^= c == '-', c = fetch();
        while (isdigit(c)) a = a * 10 + c - 48, c = fetch();
        return b ? a : -a;
    }
}

using ffastIO::read;

namespace SegTree{
    #define ls rt << 1
    #define rs rt << 1 | 1
    #define lson ls, l,
    #define rson rs, mid + 1,

    struct info{
        int lv = 0, rv = 0;
        int ans = 1, llis = 1, llds = 1, rlis = 1, rlds = 1, plm = 1, prm = 1, len = 1;
        info() {}
        info(int val): lv(val), rv(val) {}
        info operator+ (info &x) {
            info res;
            res.lv = lv, res.rv = x.rv, res.ans = max(ans, x.ans);
            res.llis = llis, res.llds = llds;
            res.rlis = x.rlis, res.rlds = x.rlds;
            res.plm = plm, res.prm = x.prm;
            res.len = len + x.len;
            if(rv < x.lv){
                if(llis == len) res.llis += x.llis;
                if(x.rlis == x.len) res.rlis += rlis;
                if(x.prm == x.len) res.prm += rlis;
                if(llis == len) res.plm = max(res.plm, len + x.plm);
                res.ans = max(res.ans, rlis + x.plm);
            }   
            else if(rv > x.lv){
                if(llds == len) res.llds += x.llds;
                if(x.rlds == x.len) res.rlds += rlds;
                if(plm == len) res.plm += x.llds;
                if(x.rlds == x.len) res.prm = max(res.prm, x.len + prm);
                res.ans = max(res.ans, prm + x.llds);
            }
            return res;
        }
    }tree[N << 2];
    
    int lazy[N << 2];

    inline void push_up(int rt){ tree[rt] = tree[ls] + tree[rs]; }

    inline void push_down(int rt){
        if(!lazy[rt]) return;
        tree[ls].lv += lazy[rt], tree[ls].rv += lazy[rt];
        tree[rs].lv += lazy[rt], tree[rs].rv += lazy[rt];
        lazy[ls] += lazy[rt], lazy[rs] += lazy[rt];
        lazy[rt] = 0;
    }

    void build(int rt, int l, int r){
        lazy[rt] = 0;
        if(l == r) return (void)(tree[rt] = info(a[l]));
        int mid = l + r >> 1;
        build(lson), build(rson);      
        push_up(rt);
    }

    void update(int rt, int l, int r, int L, int R, int val){
        if(l >= L && r <= R){
            tree[rt].lv += val, tree[rt].rv += val;
            lazy[rt] += val;
            return;
        }
        push_down(rt);
        int mid = l + r >> 1;
        if(mid >= L) update(lson, L, R, val);
        if(mid < R) update(rson, L, R, val);
        push_up(rt);
    }
}

#define SEGRG 1, 1,

inline void solve(){
    int n = read();
    for(int i = 1; i <= n; i++) a[i] = read();
    SegTree::build(SEGRG);
    int m = read();
    for(int i = 1; i <= m; i++){
        int l = read(), r = read(), d = read();
        SegTree::update(SEGRG, l, r, d);
        cout << SegTree::tree[1].ans << endl;
    }
}

signed main(){
    solve();
    return 0;
}