萌新求助,线段树$TLE$

P1886 滑动窗口 /【模板】单调队列

Fraction @ 2018-09-16 15:49:48

RT,无比正常的线段树,难道是线段树常数GG?

贴代码:

// luogu-judger-enable-o2
#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 ll long long
#define il inline
using namespace std;

template <typename T> il void read(T &dig) {
    bool flag = false;
    char c = getchar();
    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;
}

const int inf = INT_MAX;
const int MAXN = (int)4e6 + 5;

int n, k;
int num[MAXN];

class Segment {
    #define MTH 1
    public:
        Segment() {return ;}
        ~Segment() {return ;}
    #undef MTH

    #define YHB 2
    protected:
        int maxn[MAXN], minn[MAXN];
    #undef YHB

    #define HKH 3
    public:
        il int ls(int node) {return node << 1;}

        il int rs(int node) {return node << 1 | 1;}

        il void build(int node, int l, int r) {
            if(l == r) {
                maxn[node] = num[l];
                minn[node] = num[l];
                return ;
            } else {
                int mid = (l + r) >> 1;
                build(ls(node), l, mid);
                build(rs(node), mid+1, r);
                maxn[node] = max(maxn[ls(node)], maxn[rs(node)]);
                minn[node] = min(minn[ls(node)], minn[rs(node)]);
            }
        }

        il int query_max(int node, int wantl, int wantr, int nowl, int nowr) {
            int ret = -inf;
            if(wantl <= nowl && nowr <= wantr) {
                return maxn[node];
            } else {
                int mid = (nowl + nowr) >> 1;
                if(wantl <= mid) ret = max(ret, query_max(ls(node), wantl, wantr, nowl, mid));
                if(wantr > mid) ret = max(ret, query_max(rs(node), wantl, wantr, mid+1, nowr));
            }
            return ret;
        }

        il int query_min(int node, int wantl, int wantr, int nowl, int nowr) {
            int ret = inf;
            if(wantl <= nowl && nowr <= wantr) {
                return minn[node];
            } else {
                int mid = (nowl + nowr) >> 1;
                if(wantl <= mid) ret = min(ret, query_min(ls(node), wantl, wantr, nowl, mid));
                if(wantr > mid) ret = min(ret, query_min(rs(node), wantl, wantr, mid+1, nowr));
            }
            return ret;
        }
    #undef HKH
};

Segment t;

il void init() {
    read(n), read(k);
    fp(i, 1, n) read(num[i]);
    t.build(1, 1, n);
}

il void solve() {
    fp(i, 1, n-k+1) printf("%d ", t.query_min(1, i, i+k-1, 1, n));
    printf("\n");
    fp(i, 1, n-k+1) printf("%d ", t.query_max(1, i, i+k-1, 1, n));
}

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

by The_Chaos @ 2018-09-16 15:58:13

@Fraciton 请使用单调队列

这和在线段树模板题里打分块一样不合时宜。被卡很正常。


by 一扶苏一 @ 2018-09-16 15:58:31

@Fraciton 线段树是O(nlogn)的吖……本身这个复杂度就过不去1e6的数据范围好不……


by Fraction @ 2018-09-16 16:01:21

@一扶苏一 不是能过吗


by Nero_Claudius @ 2018-09-16 16:09:53

@hsfzLZH_ 分块大法好虽然我打的zkw


by Nero_Claudius @ 2018-09-16 16:10:32

@hsfzLZH_ 话说。。。这不是线段树板子题吗?当年老师教线段树的时候就打了这道题


by 一扶苏一 @ 2018-09-16 16:39:25

@Fraciton 线段树这么大的常数1e6一般都跑不过去的吧……


by Burnside @ 2018-10-24 13:01:27

@一扶苏一 捕捉神仙 我刚打完线段树


by 一扶苏一 @ 2018-10-24 14:16:27

@Burnside 您抓到了一只蒟蒻qwq


by Burnside @ 2018-10-24 14:36:23

@一扶苏一 神仙呐qwq

我线段树a了qwq


by 一扶苏一 @ 2018-10-24 18:20:14

@Burnside 所以您神仙呐orz


| 下一页