萌新求助,线段树$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 Pecco @ 2018-11-05 16:42:08

线段树稍微优化一下可以过的


上一页 |