五色开花了，哭了

Jelly_Goat @ 2019-05-30 17:56:27

by Jelly_Goat @ 2019-05-30 17:57:08

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;
template<const size_t len,const bool mode,typename Tp_>
struct ddqueue{
    Tp_ datas[len];
    int head,tail;
    ddqueue(){
        memset(datas,0,sizeof(datas));
        head=tail=0;
    }
    inline int size() { return this->tail - this->head; }
    inline bool empty() { return this->head==this->tail; }
    inline void push_back(Tp_ data){ this->datas[++this->tail]=data; }
    inline void pop_front() { this->head++; }
    inline void pop_back() { this->tail--; }
    inline void clear() { while (this->size()) this->pop_back(); }
    inline Tp_ front() { return this->datas[this->head+1]; }
    inline Tp_ end() { return this->datas[this->tail]; }
    inline void push(Tp_ data)
    {
        if (mode)//单调递减，队头最大 
        {
            while (data < this->end()&&(!this->empty())) { this->pop_back(); }
            push_back(data);
        }
        else
        {
            while (data > this->end()&&(!this->empty())) { this->pop_back(); }
            push_back(data);
        }
    }
};
struct node{
    int num,id;
    inline friend bool operator > (const node &a,const node &b)
    {
        return a.num > b.num;
    }
    inline friend bool operator < (const node &a,const node &b)
    {
        return a.num < b.num;
    }
};
ddqueue<100001,false,node> Greater;
ddqueue<100001,true,node> Less;
int a[100001],n,k;

int main()
{
    scanf("%d%d",&n,&k);
    for (register int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    for (register int i=1;i<=k-1;i++)
    {
        Less.push((node){a[i],i});
    }
    for (register int i=k;i<=n;i++)
    {
        if (Less.front().id == i-k) Less.pop_front();
        //Less.print();
        Less.push((node){a[i],i});
        printf("%d ",Less.front().num); 
    }
    printf("\n");
    for (register int i=1;i<=k-1;i++)
    {
        Greater.push((node){a[i],i});
    }
    for (register int i=k;i<=n;i++)
    {
        if (Greater.front().id == i-k) Greater.pop_front();
        Greater.push((node){a[i],i});
        printf("%d ",Greater.front().num); 
    }
    printf("\n");
    return 0;
}

by Jelly_Goat @ 2019-05-30 17:57:41

自闭了

by SSerxhs @ 2019-05-30 18:05:32

暗示五色旗，举报了

by Jelly_Goat @ 2019-05-30 18:07:57

@SSerxhs
...五色旗是什么
是那个什么中国近代用的海军旗帜？？？

by wxwoo @ 2019-05-30 18:11:51

换线段树吧，虽然我知道线段树不是正解

by 逃课小姐MS @ 2019-05-30 18:13:02

@wxwoo +1

by wxwoo @ 2019-05-30 18:14:18

不对，不带修改应该用ST表，虽然我知道ST表也不是正解

by 斯茂 @ 2019-05-30 18:19:10

正解：LCT

by Celestial_Scarlet @ 2019-05-30 18:23:06

开花(

by Celestial_Scarlet @ 2019-05-30 18:24:10

我P代码只有不到1kb啊qwq