我觉得nlog(n)应该能过吧

#include <cstdio>
#include <cstdlib>
#include <tuple>
#define int long long
#define re register
#define get getchar()
inline int read(){
    re int x = 0 , f = 1;re char c = get;
    while (c < '0' || c > '9') f ^= !(c ^ 45) , c = get;
    while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c ^ 48) , c = get;
    return f ? x : -x;
}
struct Node{
	Node *ch[2];
	int val , prio , cnt , siz;
	Node (int val) : val(val) , cnt(1) , siz(1){
		ch[0] = ch[1] = nullptr;
		prio = rand();
	} Node (Node *_node){
		val = _node -> val , cnt = _node -> cnt , siz = _node -> siz , prio = _node -> prio;
	} inline void upd_siz(){
		siz = cnt;
		if (ch[0] != nullptr) siz += ch[0] -> siz;
		if (ch[1] != nullptr) siz += ch[1] -> siz;
	}
};
struct fhq_treap{
	Node *root;
	std::pair <Node * , Node *> split(Node *cur , re int key){
		if (cur == nullptr) return {nullptr , nullptr};
		if (cur -> val <= key){
			auto temp = split(cur -> ch[1] , key);
			cur -> ch[1] = temp.first;
			cur -> upd_siz();
			return {cur , temp.second};
		} else{
			auto temp = split(cur -> ch[0] , key);
			cur -> ch[0] = temp.second;
			cur -> upd_siz();
			return {temp.first , cur};
		}
	} std::tuple <Node * , Node * , Node *> split_by_rk(Node *cur , re int rk){
		if (cur == nullptr) return {nullptr , nullptr , nullptr};
		re int ls_size = (cur -> ch[0] == nullptr ? 0 : cur -> ch[0] -> siz);
		if (rk <= ls_size){
			Node *l , *mid , *r;
			std::tie(l , mid , r) = split_by_rk(cur -> ch[0] , rk);
			cur -> ch[0] = r;
			cur -> upd_siz();
			return {l , mid , cur};
		} else if (rk <= ls_size + cur -> cnt){
			Node *lt = cur -> ch[0];
			Node *rt = cur -> ch[1];
			cur -> ch[0] = cur -> ch[1] = nullptr;
			return {lt , cur , rt};
		} else{
			Node *l , *mid , *r;
			std::tie(l , mid , r) = split_by_rk(cur -> ch[1] , rk - ls_size - cur -> cnt);
			cur -> ch[1] = l;
			cur -> upd_siz();
			return {cur , mid , r};
		}
	} Node* merge(Node* u , Node* v){
		if (u == nullptr && v == nullptr) return nullptr;
		if (u == nullptr && v != nullptr) return v;
		if (u != nullptr && v == nullptr) return u;
		if (u -> prio < v -> prio){
			u -> ch[1] = merge(u -> ch[1] , v);
			u -> upd_siz();
			return u;
		} else{
			v -> ch[0] = merge(u , v -> ch[0]);
			v -> upd_siz();
			return v;
		}
	} inline void del(re int val){
        auto tmp = split(root , val);
        auto ltr = split(tmp.first , val - 1);
        if (ltr.second -> cnt > 1){
            -- ltr.second -> cnt;
            ltr.second -> upd_siz();
            ltr.first = merge(ltr.first , ltr.second);
        }
        else{
            if (tmp.first == ltr.second) tmp.first = nullptr;
            delete ltr.second;
            ltr.second = nullptr;
        }
        root = merge(ltr.first , tmp.second);
    } inline void insert(re int val){
		auto temp = split(root , val);
		auto l_tr = split(temp.first , val - 1);
		Node *new_node;
		if (l_tr.second == nullptr) new_node = new Node(val);
		else{
			++ l_tr.second -> cnt;
			l_tr.second -> upd_siz();
		}
		Node *l_tr_combined = merge(l_tr.first , l_tr.second == nullptr ? new_node : l_tr.second);
		root = merge(l_tr_combined , temp.second);
	} inline int qval_by_rank(Node *cur , re int rk){
		Node *l , *mid , *r;
		std::tie(l , mid , r) = split_by_rk(cur , rk);
		re int ret = mid -> val;
		root = merge(merge(l , mid) , r);
		return ret;
	}
}tr;
const int MAXN = 1e6 + 1;
int a[MAXN] , b[MAXN] , c[MAXN];
signed main(){
    srand(199994954);
    re int n = read() , k = read();
    for (re int i = 1;i <= k;++ i){
        c[i] = read();
        tr.insert(c[i]);
    }
    a[1] = tr.qval_by_rank(tr.root , 1);
    b[1] = tr.qval_by_rank(tr.root , k);
    for (re int i = k + 1;i <= n;++ i){
        tr.del(c[i - k]);
        c[i] = read();
        tr.insert(c[i]);
        a[i - k + 1] = tr.qval_by_rank(tr.root , 1);
        b[i - k + 1] = tr.qval_by_rank(tr.root , k);
    }
    for (re int i = 1;i <= n - k + 1;++ i) printf("%d " , a[i]);
    putchar('\n');
    for (re int i = 1;i <= n - k + 1;++ i) printf("%d " , b[i]);
    return 0;
}