样例都过不去,查不出错,球球了/kk
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 3e5 + 5;
int n, m, a[N];
struct node{
int lv, rv, lx, rx, ldec, rinc, ans, tag, len;
friend node operator +(const node a, const node b) {
node c;
c.lv = a.lv, c.rv = b.rv;
c.ldec = a.ldec; if(a.ldec == a.len && a.rv > b.lv) c.ldec += b.ldec;
c.rinc = b.rinc; if(b.rinc == b.len && a.rv < b.lv) c.rinc += a.rinc;
c.lx = a.lx; if(a.lx == a.len && a.rv > b.rv) c.lx += b.ldec;
if(a.rinc == a.len) c.lx = max(c.lx, a.rinc + b.ldec);
if(a.rinc == a.len && a.rv < b.lv) c.lx = max(c.lx, a.rinc + b.lx);
c.rx = b.rx; if(b.rx == b.len && a.rv < b.lv) c.rx += a.rinc;
if(b.ldec == b.len) c.rx = max(c.rx, a.rinc + b.ldec);
if(b.ldec == b.len && a.rv > b.lv) c.rx = max(c.rx, a.rx + b.ldec);
c.ans = max(a.rinc + b.ldec, max(a.ans, b.ans));
if(a.rx < b.lx) c.ans = max(c.ans, a.rinc + b.lx);
if(a.rx > b.lx) c.ans = max(c.ans, a.rx + b.ldec);
c.len = a.len + b.len;
return c;
}
};
namespace Seg{
node tr[N << 2];
void pushup(int cur) { return tr[cur] = tr[cur << 1] + tr[cur << 1 | 1], void();}
void build(int cur, int lt, int rt) {
if(lt == rt) {
tr[cur] = {a[lt], a[lt], 1, 1, 1, 1, 1, 0, 1};
return ;
}
int mid = lt + rt >> 1;
build(cur << 1, lt, mid); build(cur << 1 | 1, mid + 1, rt);
return pushup(cur), void();
}
void addtag(int cur, int lt, int rt, int val) { return tr[cur].tag += val, tr[cur].lv += val, tr[cur].rv += val, void();}
void pushdown(int cur, int lt, int rt) {
if(!tr[cur].tag) return ;
int mid = lt + rt >> 1;
addtag(cur << 1, lt, mid, tr[cur].tag); addtag(cur << 1 | 1, mid + 1, rt, tr[cur].tag);
return tr[cur].tag = 0, void();
}
node query(int cur, int lt, int rt, int qx, int qy) {
if(qx <= lt && rt <= qy) return tr[cur];
int mid = lt + rt >> 1; pushdown(cur, lt, rt);
if(qx <= mid && qy > mid) return query(cur << 1, lt, mid, qx, qy) + query(cur << 1 | 1, mid + 1, rt, qx, qy);
else {
if(qx <= mid) return query(cur << 1, lt, mid, qx, qy);
else return query(cur << 1 | 1, mid + 1, rt, qx, qy);
}
}
void modify(int cur, int lt, int rt, int qx, int qy, int val) {
if(qx <= lt && rt <= qy) { return addtag(cur, lt, rt, val), void();}
int mid = lt + rt >> 1; pushdown(cur, lt, rt);
if(qx <= mid) modify(cur << 1, lt, mid, qx, qy, val);
if(qy > mid) modify(cur << 1 | 1, mid + 1, rt, qx, qy, val);
return pushup(cur), void();
}
}using namespace Seg;
signed main() {
scanf("%lld", &n);
for (int i = 1; i <= n; ++i) scanf("%lld", &a[i]);
Seg :: build(1, 1, n);
//cout << Seg :: query(1, 1, n, 1, n).ans << "\n";
scanf("%lld", &m);
for (int i = 1; i <= m; ++i) {
int x, y, z; scanf("%lld%lld%lld", &x, &y, &z);
Seg :: modify(1, 1, n, x, y, z);
printf("%lld\n", Seg :: query(1, 1, n, x, y).ans);
}
return 0;
}