D - Concatenate Subsequences

传送门：

https://atcoder.jp/contests/arc134/tasks/arc134_d

题意：给你一个长为2n的序列，可以在前n个数字中选出一条子序列，然后会附带给你i+n的后一半子序列（比如n为4，选了a1+a2+a4，那么会附带给你a5+a6+a8，最终序列就是a1+a2+a4+a5+a6+a8），要求该序列字典序最小。

分析：细节题。显然可以不断地在[l=1,r=n]的区间中贪心的找到最小数字后更新l，那么第一次会得到a1+a5（第一小的数字子序列a1 和 对应的子序列a5），这里要判断a5中的最小值是否小于等于a1的值。之后选择a2+a6，这里要根据a2的值与后一半被动加入的序列大小 判断a2能否加入。因为要用到每个值对应的位置，故先离散化。因为要多次查询区间最值，故预处理st表。

代码：

#include
using namespace std;
#define int long long
const int maxn=2e5;
const int maxlog=20;
int a[maxn];
int aa[maxn];
int b[maxn];
vectorv[maxn];
int ansp[maxn];
int table[maxn][maxlog];
int n;
sets[maxn];
map,int>mp;
int cntt;

void pre()
{
	memcpy(aa,a,sizeof a);
	sort(aa+1,aa+2*n+1);
	int cnt=unique(aa+1,aa+2*n+1)-aa-1;
	for(int i=1;i<=2*n;i++)
	{
        b[i]=lower_bound(aa+1,aa+cnt+1,a[i])-aa;
        table[i][0]=b[i];
	}
	for(int st=1;(1<>n;
	for(int i=1;i<=2*n;i++)
	{
		cin>>a[i];
	}
	pre();
	int l=1,r=n;
	while(1)
	{
		if(l>r) break;
		int st=__lg(r-l+1);
		int x=min(table[l][st],table[r-(1<=l)
				{
					ansp[++cntt]=v[x][i];
				}
			}
		}
		l=v[x][v[x].size()-1]+1;
	}
	for(int i=1;i<=cntt;i++)
	{
		cout<