新人求助,线段树死活$RE2 RE10$

P1440 求m区间内的最小值

Fraction @ 2018-08-24 16:06:16

RT,线段树是要开4倍空间,然鹅我开了10倍还是RE

#include <bits/stdc++.h>
#define fp(i, l, r) for(register int i  =(l); i <= (r); ++i)
#define fd(i, l, r) for(register int i  =(l); i >= (r); --i)
#define ANTISYNC ios::sync_with_stdio(false)
#define full(a, b) memset(a, b, sizeof(a))
#define GIVENTIE cin.tie(0); cout.tie(0)
#define MAXN (int)2e6 + 5
#define ll long long
#define il inline
#define SAFE 4
using namespace std;

template <typename T> il void read(T &dig) {
    char c = getchar();
    bool flag = false;
    dig = 0;
    while(!isdigit(c) && c != '-') c = getchar();
    if(c == '-') flag = true, c = getchar();
    while(isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if(flag) dig = -dig;
}

int n, m;
int tree[MAXN * 10], num[MAXN * 10];

namespace Segment {
    il int ls(int node) {return node << 1;}
    il int rs(int node) {return node << 1 | 1;}
    il int build(int node, int l, int r) {
        if(l == r) {
            tree[node] = num[l];
            return 0;
        }
        int mid = (l+r) >> 1;
        build(ls(node), l, mid);
        build(rs(node), mid+1, r);
        tree[node] = min(tree[ls(node)], tree[rs(node)]);
        return 0;
    }
    il int query(int node, int wantl, int wantr, int nowl, int nowr) {
        int ret  = INT_MAX;
        if(wantl <= nowl && nowr <= wantr) {
            return tree[node];
        }
        int mid = (nowl+nowr) >> 1;
        if(wantl <= mid) ret = min(ret, query(ls(node), wantl, wantr, nowl, mid));
        if(wantr > mid) ret = min(ret, query(rs(node), wantl, wantr, mid+1, nowr));
        return ret;
    }
};

using namespace Segment;

il int init() {
    read(n), read(m);
    fp(i, 1, n) read(num[i]);
    build(1, 1, n);
    printf("0\n");
    fp(i, 2, n) {
        if(i <= m+1) {
            printf("%d\n", query(1, 1, i-1, 1, n));
        } else printf("%d\n", query(1, i-m, i-1, 1, n));
    }
    return 0;
}

int main() {
    init();
    return 0;
}

优雅的orz


by 引领天下 @ 2018-08-24 16:08:15

@Fraciton 我怀疑您是数组太大了所以RE了……新人就写namespace?新人就做线段树?新人就红了?

orz

by A星际穿越 @ 2018-08-24 16:09:20

洛谷初学OI就红名吊打大佬系列


by Fraction @ 2018-08-24 16:09:35

@引领天下 gg,我一开始是数组开小了RE 然后开4RE 现在开10倍还是RE 应该不是这个问题吧...orz


by A星际穿越 @ 2018-08-24 16:11:37

重构代码吧这是最快的调代码方式


|