线段树

#include<bits/stdc++.h>
using namespace std;
#define lu (u<<1)
#define ru (u<<1|1)
const int N=4e5+10;
int n,tr[N*4],p[N],d[N];
vector<int>e[N];set<int>s;
priority_queue<int,vector<int>,greater<int>>q;
int mn(int x,int y){return p[x]<p[y]?x:y;}
void pushup(int u,int l,int r,int x)
{
	if(l==r)return;
	int m=(l+r)>>1;
	if(x<=m)pushup(lu,l,m,x);
	else pushup(ru,m+1,r,x);
	tr[u]=mn(tr[lu],tr[ru]);
}
void bt(int u,int l,int r)
{
	if(l==r){tr[u]=l;return;}
	int m=(l+r)>>1;
	bt(lu,l,m);bt(ru,m+1,r);
	tr[u]=mn(tr[lu],tr[ru]);
}
int query(int u,int l,int r,int x)
{
	if(r<=x)return tr[u];
	int m=(l+r)>>1;
	if(x<=m)return query(lu,l,m,x);
	return mn(query(lu,l,m,x),query(ru,m+1,r,x));
}
void add(int r,int x)
{
	while(r)
	{
		r=query(1,1,n*2,r);
		if(p[r]>x)break;
		q.push(d[r]);
		s.insert(r);r--;
	}
}
int main()
{
	scanf("%d",&n);
	for(int i=1,x;i<=2*n;i++)
	{
		scanf("%d",&x);
		e[x].push_back(i);
	}
	for(int i=0;i<=2*n;i++)p[i]=2*n+1;
	for(int i=1;i<=n;i++)
		p[e[i][0]]=e[i][1],d[e[i][0]]=i;
	s.insert(0);s.insert(n*2+1);
	bt(1,1,2*n);add(2*n,2*n);
	for(int i=1;i<=n;i++)
	{
		int x=q.top(),y=e[x][0];q.pop();
		printf("%d %d ",x,x);
		p[y]=2*n+1;pushup(1,1,n*2,y);
		s.erase(y);
		add((*s.lower_bound(y))-1,p[*prev(s.lower_bound(y))]-1);
	}
	return 0;
}