线段树是过不去了吗?

P1440 求m区间内的最小值

低熵体 @ 2019-03-13 00:28:36


#include <cstdio>
#include <cctype>

const int INF = 2147483647;

int getint()
{
    register int x = 0;
    register char ch = 0;
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 0x30), ch = getchar();
    return x;
}

struct Segtree {
    int t[2000005 << 2], ls[2000005 << 2], rs[2000005 << 2];

    inline int lson(int p) {
        return p << 1;
    }

    inline int rson(int p) {
        return p << 1 | 1;
    }

    inline int min(int a, int b) {
        return a < b ? a : b;
    }

    void build(int l, int r, int p) {
        if (l == r) {
            t[p] = getint();
            return;
        }
        int mid = (l + r) >> 1;
        ls[p] = lson(p), rs[p] = rson(p);
        build(l, mid, ls[p]);
        build(mid + 1, r, rs[p]);

        t[p] = min(t[ls[p]], t[rs[p]]);
    }

    int query(int l, int r, int nl, int nr, int p) {
        if (l <= nl && r >= nr) return t[p];
        int mid = (nl + nr) >> 1;
        int ans = INF;
        if (l <= mid) ans = min(ans, query(l, r, nl, mid, ls[p]));
        if (r > mid) ans = min(ans, query(l, r, mid + 1, nr, rs[p]));
        return ans;
    }
} segtree;

int main()
{
    int n, m;
    n = getint(); m = getint();

    segtree.build(1, n, 1);
    printf("0\n");
    for (register int i = 1; i <= m - 1; i++)
        printf("%d\n", segtree.query(1, i, 1, n, 1));
    for (register int i = m + 1; i <= n; i++)
        printf("%d\n", segtree.query(i - m, i - 1, 1, n, 1));
    return 0;
}

by 樱初音斗橡皮 @ 2019-03-13 06:49:25

@低熵体 n这么大当然过不去,要ST表


by ニヒル @ 2019-03-13 07:18:04

@低熵体 @樱初音斗橡皮 两百万不是线性算法吗(单调队列什么的


by Mirach @ 2019-03-13 07:34:09

可以排序后用链表串串,O(n\log n)但绝对跑得过


by RiverFun @ 2019-03-13 08:39:58

@樱初音斗橡皮 ST表过不去,会MLE


by 樱初音斗橡皮 @ 2019-03-13 22:51:44

@ニヒル @Steve_braveman 才发现这题单调队列就可以。。。


by blackfrog @ 2019-04-18 22:48:16

@樱初音斗橡皮 我咋过不了单调队列


by 樱初音斗橡皮 @ 2019-04-19 06:46:22

@blackfrog 肯定是你打错了


|