锰锌求调线段树
查看原帖
锰锌求调线段树
483928
Z1qqurat楼主2023/2/21 09:09

WA 了/kk

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e4 + 5, N4 = 2e5 + 5;
int n, m, a[N];
struct node{
    int lx = 0, rx = 0, ans = 0, lt = 0, rt = 0;
    friend node operator +(const node &a, const node &b) {
        node c;
        c.lx = a.lx; if(a.lx == a.rt - a.lt + 1) c.lx += b.lx;
        c.rx = b.rx; if(b.rx == b.rt - b.lt + 1) c.rx += a.rx;
        c.ans = max(a.ans, max(b.ans, a.rx + b.lx));
        return c;
    }
}tr[N4];

void pushup(int cur) {
    tr[cur] = tr[cur << 1] + tr[cur << 1 | 1];
    return ;
}

void build(int cur, int lt, int rt) {
    if(lt == rt) {
        tr[cur].lx = tr[cur].rx = tr[cur].ans = a[lt];
        tr[cur].lt = tr[cur].rt = lt;
        return ;
    }
    int mid = (lt + rt) >> 1;
    build(cur << 1, lt, mid);
    build(cur << 1 | 1, mid + 1, rt);
    pushup(cur);
    return ;
}

node query(int cur, int lt, int rt, int qx, int qy) {   
    node ret;
    if(lt > qy || rt < qx) return ret;
    if(lt >= qx && rt <= qy) return tr[cur];
    int mid = (lt + rt) >> 1;
    return query(cur << 1, lt, mid, qx, qy) + query(cur << 1 | 1, mid + 1, rt, qx, qy);
}

signed main() {
    scanf("%lld", &n);
    for (int i = 1; i <= n; ++i) scanf("%lld", &a[i]);
    build(1, 1, n);
    scanf("%lld", &m);
    for (int i = 1; i <= m; ++i) {
        int x, y; scanf("%lld%lld", &x, &y);
        printf("%lld\n", query(1, 1, n, x, y).ans);
    }
    return 0;
}
2023/2/21 09:09
加载中...