求助
查看原帖
求助
483928
Z1qqurat楼主2023/3/8 11:39

样例都过不去,查不出错,球球了/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;
}
2023/3/8 11:39
加载中...