[AtCoder] ARC 080 E: Young Maids

題目連結:http://arc080.contest.atcoder.jp/tasks/arc080_c

---

作法滿greedy的，每次都挑字典序最小的一組pair，而且中間必定要隔偶數個數字，挑出來後就可以直接寫在前面，因為這方法其實就等價於最後再挑這兩個(因為中間隔偶數個，所以中間一定可以拿完)，不過稍微再想兩下就會發現其實還可以知道每次要挑的位置是先奇數再偶數，而且每次後面那個偶數位的一定不能超過前面拔掉的位置之一，稍微處理一下這個細節大概就可以做了。

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
#define FF first
#define SS second

const int N = 200000 + 5;
const int INF = 1<<30;
class SegTree{
	private:
		int size;
		PII nodes[4*N];
		inline int lc(int x){return 2*x+1;}
		inline int rc(int x){return 2*x+2;}
		void build(int l, int r ,int id, PII arr[]){
			if(r-l==1){
				nodes[id]=arr[l];
				return;
			}
			int mid=(l+r)>>1;
			build(l, mid, lc(id), arr);
			build(mid, r, rc(id), arr);
			nodes[id] = min(nodes[lc(id)], nodes[rc(id)]);
		}
		PII query(int ql, int qr, int l, int r, int id){
			if(qr <= l or r <= ql) return {INF,INF};
			if(ql <= l and r <= qr) return nodes[id];
			int mid=(l+r)>>1;
			return min(query(ql, qr, l, mid, lc(id)), query(ql, qr, mid, r, rc(id)));
		}
		void modify(int ql, int qr, int l, int r, int id, PII v){
			if(qr <= l or r <= ql) return;
			if(ql <= l and r <= qr){
				nodes[id]=v;
				return;
			}
			int mid=(l+r)>>1;
			modify(ql, qr, l, mid, lc(id), v);
			modify(ql, qr, mid, r, rc(id), v);
			nodes[id] = min(nodes[lc(id)], nodes[rc(id)]);
		}
	public:
		void build(int n, PII arr[]){
			size=n;
			build(0, size, 0, arr);
		}
		PII query(int l, int r){
			return query(l, r, 0, size, 0);
		}
		void modify(int p, PII v){
			modify(p, p+1, 0, size, 0, v);
		}
} odd, even;

int arr[N], ans[N];
PII o[N], e[N];

int main(int argc, char* argv[]){
	int n; cin>>n;
	fill(o, o+n, (PII){INF,INF});
	fill(e, e+n, (PII){INF,INF});
	for(int i=0;i<n;i++){
		cin>>arr[i];
		if(i&1) o[i]={arr[i],i};
		else e[i]={arr[i],i};
	}
	odd.build(n, o);
	even.build(n, e);
	set<int> block;
	block.insert(0);
	block.insert(n);
	priority_queue<PII,vector<PII>,greater<PII>> pq;
	pq.push(even.query(0, n));
	for(int i=0;i<(n/2);i++){
		PII pos = pq.top();pq.pop();
		if(pos.SS & 1){
			PII sec = even.query(pos.SS, *block.upper_bound(pos.SS));
			odd.modify(pos.SS, {INF,INF});
			even.modify(sec.SS, {INF,INF});
			auto it = block.upper_bound(pos.SS);
			it--;
			pq.push(odd.query(*it, pos.SS));
			pq.push(even.query(pos.SS, sec.SS));
			pq.push(odd.query(sec.SS, *block.upper_bound(sec.SS)));
			block.insert(pos.SS);
			block.insert(sec.SS);
			ans[i*2]=pos.FF;
			ans[i*2+1]=sec.FF;
		}else{
			PII sec = odd.query(pos.SS, *block.upper_bound(pos.SS));
			even.modify(pos.SS, {INF,INF});
			odd.modify(sec.SS, {INF,INF});
			auto it = block.upper_bound(pos.SS);
			it--;
			pq.push(even.query(*it, pos.SS));
			pq.push(odd.query(pos.SS, sec.SS));
			pq.push(even.query(sec.SS, *block.upper_bound(sec.SS)));
			block.insert(pos.SS);
			block.insert(sec.SS);
			ans[i*2]=pos.FF;
			ans[i*2+1]=sec.FF;
		}
	}
	for(int i=0;i<n;i++) cout<<ans[i]<<" \n"[i==n-1];
	return 0;
}