AOJ 1070 FIMO sequence

問題

日本語なので本文参照（http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1070&lang=jp）

制約条件

クエリの数≦200000

方針

結構前に解いた奴なので忘れてる。

データ構造を、前半(n + 1) / 2個と後半n / 2個の二つに分けて持つ。
前半の数列で、末尾からk項を削除したときの最小値、最大値を求めるには、
増加列からなるデキューと、減少列からなるデキューとを使えばよい。

要素の挿入と削除増加列の中身のsetと、減少列の中身のsetを使って何かしてる……

ソースコード

const int MX = 400010;
int n, type, in[MX];
struct S{
	int *q, *inc, *dec, h, t, ih, it, dh, dt;
	set<pair<int, int> > incs, decs;
	S(){
		q = new int[MX];
		inc = new int[MX];
		dec = new int[MX];
		h = t = ih = it = dh = dt = MX / 2;
	}
	~S(){
		delete(q); delete(inc); delete(dec);
	}
	int size(){ return t - h; }
	void push(int id){
		q[t++] = id;
		if(ih < it && in[inc[it - 1]] >= in[id]) incs.insert(mp(-in[id], id));
		else inc[it++] = id;
		if(dh < dt && in[dec[dt - 1]] <= in[id]) decs.insert(mp( in[id], id));
		else dec[dt++] = id;
	}
	int pop(){
		int id = q[--t];
		set<pair<int, int> >::iterator p = incs.lower_bound(mp(-in[id], 0));
		set<pair<int, int> >::iterator q = decs.lower_bound(mp( in[id], 0));
		if(p != incs.end() && p -> second == id) incs.erase(p);
		if(q != decs.end() && q -> second == id) decs.erase(q);
		if(ih < it && inc[it - 1] == id){
			it--;
			if(!incs.empty() && -incs.begin()->first > in[inc[it - 1]])
				inc[it++] = incs.begin()->second;
		}
		if(dh < dt && dec[dt - 1] == id){
			dt--;
			if(!decs.empty() &&  decs.begin()->first < in[dec[dt - 1]])
				dec[dt++] = decs.begin()->second;
		}
		return in[id];
	}
	int get(int x){
		return in[dec[dt - x]];
	}
	int rget(int x){
		return in[inc[it - x]];
	}
};
struct T{
	int *q, *inc, *dec, h, t, ih, it, dh, dt;
	T(){
		q = new int[MX];
		inc = new int[MX];
		dec = new int[MX];
		h = t = ih = it = dh = dt = MX / 2;
	}
	~T(){
		delete(q); delete(inc); delete(dec);
	}
	int size(){ return t - h; }
	void push(int id){
		while(ih < it && in[inc[it - 1]] >= in[id]) it--;
		while(dh < dt && in[dec[dt - 1]] <= in[id]) dt--;
		q[t++] = inc[it++] = dec[dt++] = id;
	}
	int pop(){
		if(ih < it && inc[ih] == q[h]) ih++;
		if(dh < dt && dec[dh] == q[h]) dh++;
		return q[h++];
	}
	int get(int x){
		return in[inc[ih + x - 1]];
	}
	int rget(int x){
		return in[dec[dh + x - 1]];
	}
};
const bool next[] = {1, 0, 0, 0, 1, 1, 0, 0, 1, 1};

int main(){
	while(cin >> n, n){
		S s;
		T t;
		rep(it, n){
			cin >> type;
			if(next[type]) cin >> in[it];
			if(type == 0){
				t.push(it);
				if(s.size() < t.size()) s.push(t.pop());
			}
			else if(type == 1){
				cout << s.pop() << endl;
				if(s.size() < t.size()) s.push(t.pop());
			}
			else if(type == 2) cout << s.get(1)       << endl;
			else if(type == 3) cout << t.get(1)       << endl;
			else if(type == 4) cout << s.get(in[it])  << endl;
			else if(type == 5) cout << t.get(in[it])  << endl;
			else if(type == 6) cout << s.rget(1)      << endl;
			else if(type == 7) cout << t.rget(1)      << endl;
			else if(type == 8) cout << s.rget(in[it]) << endl;
			else if(type == 9) cout << t.rget(in[it]) << endl;
		}
		cout << "end" << endl;
	}
	return 0;
}