线段树绝世好题。
题意：
维护区间加，全局最长单峰序列。
Solution：
维护 \(8\) 个量。
\(lval\)：左端点的权值。
\(rval\)：右端点的权值。
\(lmax\)：以左端点开始的最长的下降序列长度。
\(rmax\)：以右端点结束的最长的上升序列长度。
\(lans\)：以左端点开始的最长的单峰序列长度。
\(rans\)：以右端点结束的最长的单峰序列长度。
\(ans\)： 区间内最长的单峰序列长度。
\(tag\)：区间加法懒标记。
考虑怎么用左右两个儿子更新父节点的信息。
用 \(lson\) 来表示左儿子，\(rson\) 来表示右儿子，\(rt\) 来表示父节点。
\(lval\)
显然父节点的 \(lval\) 是左儿子的 \(lval\)。
\(rval\)
显然父节点的 \(rval\) 是右儿子的 \(rval\)。
\(lmax\)
如果说左儿子的 \(lmax\) 等于左儿子的区间长度，说明了左区间是个下降区间，如果同时左儿子的 \(rval\) 大于了右儿子的 \(lval\) 说明了父节点的 \(lmax\) 能向右区间伸展，这个时候 \(rt.lmax = lson.lmax + rson.lmax\)。
否则无法跨过右区间，直接继承左儿子的值：\(rt.lmax = lson.lmax\)。
\(rmax\)
如果说右儿子的 \(rmax\) 等于右儿子的区间长度，说明了右区间是个上升区间，如果同时左儿子的 \(rval\) 小于了右儿子的 \(lval\) 说明了父节点的 \(rmax\) 能向左区间伸展，这个时候 \(rt.rmax = lson.rmax + rson.rmax\)。
否则无法跨过左区间，直接继承右儿子的值： \(rt.rmax = rson.rmax\)。
\(lans\)
如果说左儿子的 \(rmax\) 等于左儿子的区间长度，说明了左儿子是个上升区间。
这个时候分两种情况：
- \(lson.rval < rson.lval\) 说明了还能通过右儿子的 \(lans\) 继续扩展：\(rt.lans = lson.rmax + rson.lans\)。
-\(lson.rval > rson.lval\) 说明了只能通过右儿子的 \(lmax\) 继续扩展： \(rt.lans = lson.rmax + rson.lmax\)。
如果说左儿子的 \(lans\) 等于区间长度，想用右儿子扩展的话，必须满足 \(lson.rval > rson.lval\)，这个时候：\(rt.lans = lson.lans + rson.lmax\)。
否则无法通过右区间来更新，直接继承左儿子的值：\(rt.lans = lson.lans\)。
\(rans\)
如果说右儿子的 \(lmax\) 等于右儿子的区间长度，说明了右儿子是个下降区间。
这个时候分两种情况：
-
\(lson.rval > rson.lval\) 说明了还能通过左儿子的 \(rans\) 继续扩展：\(rt.rans = lson.rans + rson.lmax\)。
-
\(lson.rval < rson.lval\) 说明了只能通过左儿子的 \(rmax\) 继续扩展： \(rt.rans = lson.rmax + rson.lmax\)。
如果说右儿子的 \(lans\) 等于区间长度，想用左儿子扩展的话，必须满足 \(lson.rval < rson.lval\)，这个时候：\(rt.rans = lson.rmax + rson.lans\)。
否则无法通过右区间来更新，直接继承左儿子的值：\(rt.rans = rson.rans\)。
\(ans\)
答案可能是左右儿子答案的最大值。
也可能是 $lson.rmax $ 和 \(rson.lmax\) 接起来。
也可能是 \(lson.lans\) 和 \(rson.lmax\) 接起来。
也可能是 \(rson.rans\) 和 \(lson.rmax\) 接起来。
最后取个 \(\max\) 就行了。
然后修改就是普通的区间修改。
/**
* author: TLE_Automation
* creater: 2022.8.28
**/
#include<cmath>
#include<queue>
#include<cstdio>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#define gc getchar
#define INF 0x3f3f3f3f
#define int long long
using namespace std;
typedef long long ll;
const int Maxn = 6e5 + 10;
const int mod = 998244353;
const ll inf = 0x3f3f3f3f3f3f3f3f;
#define debug cout << "i ak ioi" << "\n"
inline void print(int x) {if (x < 0) putchar('-'), x = -x; if(x > 9) print(x / 10); putchar(x % 10 + '0');}
inline char readchar() {static char buf[100000], *p1 = buf, *p2 = buf; return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;}
inline int read() { int res = 0, f = 0; char ch = gc();for (; !isdigit(ch); ch = gc()) f |= (ch == '-'); for (; isdigit(ch); ch = gc()) res = (res << 1) + (res << 3) + (ch ^ '0'); return f ? -res : res;}
namespace Seg {
#define lson rt << 1
#define rson rt << 1 | 1
struct Node { int l, r, len, lval, rval, lmax, rmax, lans, rans, ans, tag; } tree[Maxn << 2];
void pushup(int rt) {
tree[rt].lval = tree[lson].lval, tree[rt].rval = tree[rson].rval;
if(tree[lson].lmax == tree[lson].len && tree[lson].rval > tree[rson].lval)
tree[rt].lmax = tree[lson].lmax + tree[rson].lmax;
else tree[rt].lmax = tree[lson].lmax;
if(tree[rson].rmax == tree[rson].len && tree[rson].lval > tree[lson].rval)
tree[rt].rmax = tree[rson].rmax + tree[lson].rmax;
else tree[rt].rmax = tree[rson].rmax;
if(tree[lson].rmax == tree[lson].len && tree[lson].rval < tree[rson].lval)
tree[rt].lans = tree[lson].rmax + tree[rson].lans;
else if(tree[lson].rmax == tree[lson].len && tree[lson].rval > tree[rson].lval)
tree[rt].lans = tree[lson].rmax + tree[rson].lmax;
else if(tree[lson].lans == tree[lson].len && tree[lson].rval > tree[rson].lval)
tree[rt].lans = tree[lson].lans + tree[rson].lmax;
else tree[rt].lans = tree[lson].lans;
if(tree[rson].lmax == tree[rson].len && tree[rson].lval < tree[lson].rval)
tree[rt].rans = tree[rson].rans + tree[lson].rans;
else if(tree[rson].lmax == tree[rson].len && tree[rson].lval > tree[lson].rval)
tree[rt].rans = tree[rson].rans + tree[lson].rmax;
else if(tree[rson].rans == tree[rson].len && tree[lson].rval < tree[rson].lval)
tree[rt].rans = tree[rson].rans + tree[lson].rmax;
else tree[rt].rans = tree[rson].rans;
tree[rt].ans = max(tree[lson].ans, tree[rson].ans);
if(tree[lson].rval != tree[rson].lval )tree[rt].ans = max(tree[rt].ans, tree[lson].rmax + tree[rson].lmax);
if(tree[lson].rval < tree[rson].lval) tree[rt].ans = max(tree[rt].ans, tree[lson].rmax + tree[rson].lans);
if(tree[lson].rval > tree[rson].lval) tree[rt].ans = max(tree[rt].ans, tree[rson].lmax + tree[lson].rans);
}
void build(int rt, int l, int r) {
tree[rt].len = r - l + 1;
tree[rt].l = l, tree[rt].r = r;
if(l == r) {
int x = read();
tree[rt].lval = tree[rt].rval = x;
tree[rt].lmax = tree[rt].rmax = 1;
tree[rt].lans = tree[rt].rans = tree[rt].ans = 1;
return;
}
int mid = (l + r) >> 1;
build(lson, l, mid), build(rson, mid + 1, r);
pushup(rt);
}
void pushdown(int rt) {
if(!tree[rt].tag) return;
tree[lson].tag += tree[rt].tag, tree[rson].tag += tree[rt].tag;
tree[lson].lval += tree[rt].tag, tree[lson].rval += tree[rt].tag;
tree[rson].lval += tree[rt].tag, tree[rson].rval += tree[rt].tag;
tree[rt].tag = 0;
}
void change(int rt, int l, int r, int k) {
if(tree[rt].l > r || tree[rt].r < l) return;
if(tree[rt].l >= l && tree[rt].r <= r) {
tree[rt].lval += k, tree[rt].rval += k, tree[rt].tag += k; return;
} pushdown(rt);
change(lson, l, r, k), change(rson, l, r, k), pushup(rt);
}
}
using namespace Seg;
signed main()
{
// freopen("in.in", "r", stdin);
// freopen("baoli.out", "w", stdout);
int n = read();
build(1, 1, n);
int Q = read();
for(int i = 1; i <= Q; i++) {
int l = read(), r = read(), k = read();
change(1, l, r, k), printf("%lld\n", tree[1].ans);
}
return (0 - 0);
}
/**
* _ooOoo_
* o8888888o
* 88" . "88
* (| -_- |)
* O\ = /O
* ___/`---'\____
* . ' \\| |// `.
* / \\||| : |||// \
* / _||||| -:- |||||- \
* | | \\\ - /// | |
* | \_| ''\---/'' | |
* \ .-\__ `-` ___/-. /
* ___`. .' /--.--\ `. . __
* ."" '< `.___\_<|>_/___.' >'"".
* | | : `- \`.;`\ _ /`;.`/ - ` : | |
* \ \ `-. \_ __\ /__ _/ .-` / /
* ======`-.____`-.___\_____/___.-`____.-'======
* ` =---='
* .............................................
* 佛曰：bug泛滥，我已瘫痪！
*/