线段树写法,只过了subtask1
查看原帖
线段树写法,只过了subtask1
86973
花园Serena楼主2020/11/9 18:51

RT,用的线段树写法,但是被subtask2给hack掉了,不知道错在哪里,求解答,代码如下

#include <bits/stdc++.h>
using namespace std;
#define rg register int
#define mid ((x + y) >> 1)
#define rs (i << 1 | 1)
#define ls (i << 1)
const int MAXN = 200000 + 10;
int n, L, R, t[(MAXN << 2) + 10], a[MAXN << 1];
int mx, f[MAXN << 1], Max = -0x7fffffff;
void inline built (int i, int x, int y) {
    if(x == y) {t[i] = a[x]; return;}
    built (ls, x, mid); built(rs, mid + 1, y);
    t[i] = max(t[rs], t[ls]);
}
int inline ans (int i, int x, int y, int l, int r) {
    if(x > r || y < l) return -0x7fffffff;
    if(x >= l && y <= r) return t[i];
    return max(ans(rs, mid + 1, y, l, r), ans(ls, x, mid , l, r));
    
}
void inline change(int i, int x, int y,int l, int w) {
    if(x == y) {t[i] = w; return;}
    if(l <= mid) change(ls, x, mid, l, w);
    else change(rs, mid + 1, y, l, w);
    t[i] = max(t[rs], t[ls]);
}
int main() {
    scanf("%d%d%d", &n, &L, &R);
    for(rg i = 0; i <= n; i ++)
        scanf("%d", &a[i]);
    for(rg i = L; i <= n + R; i ++) {
        if(i - R < 0) mx = ans(1, 0, n, 0, i - L);
        else mx = ans(1, 0, n, i - R, i - L);
        f[i] = mx + a[i]; change(1, 0, n, i, f[i]);
        if(i >= n) Max = max(f[i], Max);
    }
    printf("%d\n", Max);
    return 0;
}
2020/11/9 18:51
加载中...