萌新刚学OI求助qwq

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

bit_ @ 2019-11-02 01:02:48

啊又是窝窝线段树又双叒叕写挂了qwq

#include <bits/stdc++.h>
#define int long long

using namespace std;

void Build(int, int, int);

inline void PushUp(int);

int Min(int, int, int, int, int);

int Max(int, int, int, int, int);

inline int Read();

int n, m;

int scan[11451400], tree[191981000], _tree[191981000];

signed main(signed argc, char* argv[])
{
//  freopen("testdata.in", "r", stdin);
//  freopen("testdata.out", "w", stdout);
    n = Read(), m = Read();
    for(register int i = 1; i <= n; i++)
    {
        scan[i] = Read();
    }
    Build(1, n, 1);
    for(register int i = 1; i <= n - m + 1; i++)
    {
        printf("%d ", Min(1, n, i, i + m - 1, 1));
    }
    putchar('\n');
    for(register int i = 1; i <= n - m + 1; i++)
    {
        printf("%d ", Max(1, n, i, i + m - 1, 1));
    }
    return 0;
}

void Build(int left, int right, int root)
{
    if(left == right)
    {
        tree[root] = _tree[root] = scan[left];
        return;
    }
    else
    {
        int mid = (left + right) >> 1;
        Build(left, mid, root << 1);
        Build(mid + 1, right, root << 1 | 1);
        PushUp(root);
    }
}

inline void PushUp(int root)
{
    tree[root] = min(tree[root << 1], tree[root << 1 | 1]);
    _tree[root] = max(_tree[root << 1], _tree[root << 1 | 1]);
    return;
}

int Min(int left, int right, int from, int to, int root)
{
    if(left >= from && right <= to)
    {
        return tree[root];
    }
    else
    {
        int mid = (left + right) >> 1;
        int ans = 0x7f7f7f7f;
        if(mid >= from) ans = min(ans, Min(left, mid, from, to, root << 1));
        if(mid < to) ans = min(ans, Min(mid + 1, right, from, to, root << 1 | 1));
        return ans;
    }
}

int Max(int left, int right, int from, int to, int root)
{
    if(left >= from && right <= to)
    {
        return _tree[root];
    }
    else
    {
        int mid = (left + right) >> 1;
        int ans = 0;
        if(mid >= from) ans = max(ans, Max(left, mid, from, to, root << 1));
        if(mid < to) ans = max(ans, Max(mid + 1, right, from, to, root << 1 | 1));
        return ans;
    }
}

inline int Read()
{
    int d = 0, o = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-') o = 0;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        d = (d << 1) + (d << 3) + (ch ^ 48);
        ch = getchar();
    }
    return (o ? d : ~d + 1);
}

by bit_ @ 2019-11-02 01:03:17

WA #2, #3, #7


by MakiseVon @ 2019-11-02 02:16:04

@bit_ 大概是 Max()ans 应初始化为 -inf qwq


by HaveFun @ 2019-11-02 07:10:41

数组太大了叭


by wwlw @ 2019-11-02 07:46:54

这不是单调队列?


by Tarsal @ 2019-11-02 08:13:04

这不是单调队列?


|