1070-FIMO squence

問題概要

日本語なので略

解法

前半部分と後半部分に考えて分けて考える．
前半部分は後入れ後出し，後半部分は後入れ先出しの構造になる．
前半部分について，x番目の最大値(最小値)を求めるのは今までの最大値(最小値)を記録すれば可能
後半部分については，単調増加(減少)になるように配列に数値を入れていくようにする．

実装(C++)

#include <iostream>
#include <deque>
#include <algorithm>
#include <iterator>
#include <cstdio>
using namespace std;
struct FIMO_seqence{
  struct first_half{
    deque<int> data;
    deque<int> MAX,MIN;
    void add(int x){
      data.push_back(x);
      if(data.size()==1u){
        MAX.push_back(x);
        MIN.push_back(x);
      }else{
        if(MAX.back()<x){
          MAX.push_back(x);
        }
        if(MIN.back()>x){
          MIN.push_back(x);
        }
      }
    }
    int remove(){
      int x=data.back();
      data.pop_back();
      if(MIN.back()==x)MIN.pop_back();
      if(MAX.back()==x)MAX.pop_back();
      return x;
    }
    int size() const{
      return data.size();
    }
  } fh;
  struct second_half{
    deque<int> data;
    deque<int> MAX,MIN;
    void add(int x){
      data.push_back(x);
      if(data.size()==1u){
        MAX.push_back(x);
        MIN.push_back(x);
      }else{
        while((!MAX.empty())&&MAX.back()<x){
          MAX.pop_back();
        }
        while((!MIN.empty())&&MIN.back()>x){
          MIN.pop_back();
        }
        MAX.push_back(x);
        MIN.push_back(x);
      }
    }
    int remove(){
      int x=data.front();
      data.pop_front();
      if(MIN.front()==x)MIN.pop_front();
      if(MAX.front()==x)MAX.pop_front();
      return x;
    }
    int size() const{
      return data.size();
    }
  } sh;
  int size(){
    return sh.size()+fh.size();
  }
  void add(int x){
    sh.add(x);
    if(sh.size()>fh.size()){
      fh.add(sh.remove());
    }
  }
  int remove(){
    int r=fh.remove();
    if(sh.size()>fh.size()){
      fh.add(sh.remove());
    }
    return r;
  }
  int min_fh(int x){
    return *(fh.MIN.end()-x);
  }
  int min_sh(int x){
    return *(sh.MIN.begin()+x-1);
  }
  int max_fh(int x){
    return *(fh.MAX.end()-x);
  }
  int max_sh(int x){
    return *(sh.MAX.begin()+x-1);
  }
};
int main() {
  while(1){
    int q;
    scanf("%d",&q);
    if(q==0)break;
    FIMO_seqence fimo;
    for(int i=0;i<q;i++){
      int qt,t;
      scanf("%d",&qt);
      switch(qt){
        case 0:
          scanf("%d",&t);
          fimo.add(t);
          break;
        case 1:
          printf("%d\n",fimo.remove());
          break;
        case 2:
          printf("%d\n",fimo.min_fh(1));
          break;
        case 3:
          printf("%d\n",fimo.min_sh(1));
          break;
        case 4:
          scanf("%d",&t);
          printf("%d\n",fimo.min_fh(t));
          break;
        case 5:
          scanf("%d",&t);
          printf("%d\n",fimo.min_sh(t));
          break;
        case 6:
          printf("%d\n",fimo.max_fh(1));
          break;
        case 7:
          printf("%d\n",fimo.max_sh(1));
          break;
        case 8:
          scanf("%d",&t);
          printf("%d\n",fimo.max_fh(t));
          break;
        case 9:
          scanf("%d",&t);
          printf("%d\n",fimo.max_sh(t));
          break;
      }
    }
    puts("end");
  }
  return 0;
}