BZOJ1136: [POI2009]Arc

题目大意（跟BZOJ上的不一样！！！）：

这是一道交互题！

内存限制为32MB！

先给你一个整数K(K<=1000000)，然后按顺序给你未知个整数a1~an(n<=15000000,n不输入)

要求你求出一个长度为K的字典序最大的子序列！

这是一道非常厉害，非常有想法的交互题！

但是BZOJ不支持交互，所以就变成了一个可以上来把所有数读进来再做的SB题

朴素的做法是维护一个单调递减的栈，开始的n-k个直接推入栈中，最后k个每推进去一个元素就把栈底输出并删掉（其实像是单调队列？）

这个做法在BZOJ上就可以直接AC了

但是我们要追求本真，做POI题的目的就是拓展思维

我们考虑32MB怎么做

这种内存限制下不能开O(N)的数组但是可以开O(K)的数组啊

我们可以想到，由于最后让输出长度为K的子序列，所以任何时刻只要加入这个元素之后栈中元素超过K个，这个元素就不用加入了

这样我们就得到了一种空间O(K)的做法

但是我们又面临着一个问题，在没读入完之前，我们并不知道N是多少，我们也就不知道在什么时候需要输出栈底

这里我们可以用一个小技巧，延迟K个处理，即先读入K个数，当读入第i+K个数时，我们处理读入第i个数时应该干的事情

这样我们在读入N个数后，其实只做了前N-K个数要做的事情

这些数要做的事情没有区别，都是直接扔进带空间限制的单调栈里

当我们读入完成，我们就可以处理最后K个数了，这时每次加入都输出栈底并弹出就可以了

附BZOJ上的AC代码，其实下面主函数部分就是POI官网上能AC的代码

/*************************************************************************}
{*                                                                       *}
{*                     XVI Olimpiada Informatyczna                       *}
{*                                                                       *}
{*   Zadanie: Architekci (ARC)                                           *}
{*   Plik:    carclib.c                                                  *}
{*   Autor:   Bartosz Gorski                                             *}
{*   Opis:    Biblioteka do wczytywania danych wejsciowych i wypisywania *}
{*            wyniku                                                     *}
{*                                                                       *}
{*************************************************************************/

#include <stdlib.h>
#include <stdio.h>
#include <time.h>

#define MAGIC_BEGIN -435634223
#define MAGIC_END -324556462

#define MIN_K 1
#define MAX_K 1000000
#define MAX_N 15000000
#define MIN_A 1
#define MAX_A 1000000000
#define MIN_TYP 1
#define MAX_TYP 3
#define MIN_PAR 0
#define MAX_PAR 1000000000

#define ERROR 0
#define CORRECT 1

#define unlikely(x) __builtin_expect(!!(x), 0)

static int init = 0; // czy zostala juz wywolana funkcja inicjuj()
static int lib_n; // ile biblioteka podala juz liczb
static int con_k; // ile zawodnik podal liczb

static int N, K, A, TYP, PAR; // parametry testu wczytywane z pliku
static int bre, len_sub, bou, is_end; // zmienne pomocnicze

static int rand2_status = 198402041;

static inline int rand2(int a, int b){
  rand2_status = rand2_status * 1103515245 + 12345;
  int x = rand2_status;
  if (x < 0) x = -x; // -2^31 sie nie zdarza :D
  x >>= 1;
  x = a + x % (b - a + 1);
  return x;
}

/* test losowy */
static inline int random_test()
{
    return rand2(1, A);
}

/* test z dlugim podciagiem nierosnacym */
static inline int decreasing_test()
{
    int tmp;
    if(bre == 0) {
        bre = rand2(0, (N - lib_n + 1 - len_sub));
        tmp = A;
        A -= rand2(0, (A - 1) / len_sub);
        len_sub--;
    }
    else {
        bre--;
        tmp = rand2(1, A);
    }
    return tmp;
}

/* test z dlugim podciagiem niemalejacym */
static inline int increasing_test()
{
    return bou - decreasing_test();
}

static void finish(int res, char *com)
{
    if(res == ERROR)
        printf("%s\n", com);
    exit(0);
}

/* Inicjuje dane wejsciowe i zwraca liczbe projektow */
int inicjuj()
{
    if(init == 1)
        finish(ERROR, "Program zawodnika moze wywolac funkcje inicjuj tylko raz!!!");
    init = 1;
    scanf("%d", &K);
    if (K > 0){
      TYP = 0;
      N = MAX_N + 2;
      return K;
    }
    int magic_begin, magic_end;
    scanf("%d%d", &magic_begin, &TYP);
    if(magic_begin != MAGIC_BEGIN || TYP < MIN_TYP || TYP > MAX_TYP)
        finish(ERROR, "Program zawodnika nie moze korzystac z stdin!!!");
    scanf("%d%d%d%d", &N, &K, &A, &PAR);
    if(N < 1 || N > MAX_N || N < K || K > MAX_K || A < MIN_A || A > MAX_A 
        || PAR < MIN_PAR || PAR > MAX_PAR)
        finish(ERROR, "Program zawodnika nie moze korzystac z stdin!!!");
    scanf("%d", &magic_end);
    if(magic_end != MAGIC_END)
        finish(ERROR, "Program zawodnika nie moze korzystac z stdin!!!");
    con_k = 0;
    lib_n = 0;
    is_end = 0;
    if(TYP == 2 || TYP == 3) {
        len_sub = PAR;
        bre = 0;
    }
    if(TYP == 2)
        bou = A--;
    return K;
}

/* Sluzy do wczytania ciagu reprezentujacego jakosci projektow */
int wczytaj()
{
    if(unlikely(init == 0))
        finish(ERROR, "Program zawodnika nie wywolal funkcji inicjuj!!!");
    if(unlikely(lib_n > N || is_end == 1))
        finish(ERROR, "Program zawodnika wywolal funkcje wczytaj po otrzymaniu informacji o koncu ciagu!!!");
    if(unlikely(lib_n == N))
        return 0;
    lib_n++;
    switch (TYP) {
      case 0:
        scanf("%d", &A);
        if(A == 0)
          is_end = 1;
        return A;
        break;
      case 1: return random_test(); break;
      case 2: return increasing_test(); break;
      case 3: return decreasing_test(); break;
      default:
              finish(ERROR, "Nieznany typ testu");
    }
    return -1;
}

/* Sluzy do wypisania wyznaczonego podciagu */
void wypisz(int jakoscProjektu)
{
    if(init == 0)
        finish(ERROR, "Program zawodnika nie wywolal funkcji inicjuj!!!");
    printf("%d\n", jakoscProjektu);
    if(++con_k == K)
        finish(CORRECT, "");
}


#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 1000010
using namespace std;
int a[N],s[N],h=1,t,k;
void push(int x)
{
	while(h<=t&&s[t]<x) t--;
	if(t==k) return;
	t++;s[t]=x;
}
int main()
{
	k=inicjuj();
	int i,j,x,y;
	for(i=1;i<=k;i++)
	a[i]=wczytaj();
	int now=1;
	while(x=wczytaj())
	{
		push(a[now]);
		a[now]=x;
		now++;
		if(now==k+1) now=1;
	}
	j=now;
	do
	{
		push(a[j]);
		printf("%d\n",s[h]);
		h++;
		j++;
		if(j==k+1) j=1;
	}while(j!=now);
}