ARC141C Bracket and Permutation 做题记录

给你两个 $2n$ 的排列 $P,Q$，你要构造一个长 $2n$ 的括号序列 $S$。定义一个 $2n$ 的排列 $C$ 是合法的，当且仅当按照 $S_{C_1}S_{C_2}\cdots S_{C_{2n}}$ 是合法括号序列。你构造的 $S$ 要满足 $P$ 是字典序最小的合法排列，$Q$ 是最大的。

$1\le n\le 2\times 10^5$。

首先不难发现，若 $P_1\not= 1$，那么 $S_{[1,P_1-1]}$ 一定都是 )，并且 $S_{P_1}$ 是 (，并且 $S_{P_i}$ 接下来长 $2(P_1-1)$ 的一段一定是 ()()()() 这样的。

这个似乎没什么用，继续观察。

这种只有 $+1$ 和 $-1$ 的序列不妨考虑折线图。

不难发现，()()()() 等价于把在 $y=0$ 下方的折线拉回来，而折线原本就在 $y=0$ 上方的部分在 $P$ 中不会被修改。

所以，根据 $P$ 可以确认折线图 $y=0$ 上方的部分，根据 $Q$ 可以确认折线图 $y=0$ 下方的部分，这符合我们初步观察的结论。

那么直接模拟即可。

代码如下：

#include <iostream>
#include <cstdio>
#include <set>
#include <vector>
#include <queue>

using namespace std;

const int S=400005;

int n;
int a[S],b[S];
char s[S];
int c[S],d[S];

inline void calca()
{
	set<int> st;
	for(int i=1;i<=n;i++) st.insert(i);
	for(int i=1;i<=n&&!st.empty();i++)
	{
		if(a[i]==*st.begin())
		{
			int j=i;
			s[a[j]]='(';
			for(;j<=n&&!st.empty()&&a[j]==*st.begin();j++)
			{
				st.erase(a[j]);
			}
			j--;
			s[a[j]]=')';
			i=j;
		}
		else
		{
			int tot=0;
			while(!st.empty()&&*st.begin()<a[i])
			{
				s[*st.begin()]=')';
				st.erase(st.begin());
				tot++;
			}
			if(tot==0) return;
			for(int j=i;j<=i+tot*2-1;j+=2)
			{
				s[a[j]]='(';
				st.erase(a[j]);
			}
			i=i+tot*2-1;
		}
	}
}

inline void calcb()
{
	set<int,greater<int> > st;
	for(int i=1;i<=n;i++) st.insert(i);
	for(int i=1;i<=n&&!st.empty();i++)
	{
		if(b[i]==*st.begin())
		{
			int j=i;
			s[b[j]]='(';
			for(;j<=n&&!st.empty()&&b[j]==*st.begin();j++)
			{
				st.erase(b[j]);
			}
			j--;
			s[b[j]]=')';
			i=j;
		}
		else
		{
			int tot=0;
			while(!st.empty()&&*st.begin()>b[i])
			{
				s[*st.begin()]=')';
				st.erase(st.begin());
				tot++;
			}
			if(tot==0) return;
			for(int j=i;j<=i+tot*2-1;j+=2)
			{
				s[b[j]]='(';
				st.erase(b[j]);
			}
			i=i+tot*2-1;
		}
	}
}

int main()
{
	scanf("%d",&n);
	n*=2;
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n;i++) scanf("%d",&b[i]);
	calca();
//	puts("fina");
//	for(int i=1;i<=n;i++) printf("%c",s[i]==0?'.':s[i]);
//	printf("\n");
	calcb();
//	for(int i=1;i<=n;i++) printf("%c",s[i]==0?'.':s[i]);
//	printf("\n");
//	puts("fin");
	for(int i=1;i<=n;i++) if(s[i]==0) return puts("-1"),0;
	int c0=0;
	for(int i=1;i<=n;i++) c0+=s[i]=='(';
	if(c0!=n/2) return puts("-1"),0;
	queue<int> v0,v1;
	for(int i=1;i<=n;i++)
	{
		if(s[i]=='(') v0.push(i);
		else v1.push(i);
	}
	for(int i=1,k=0;i<=n;i++)
	{
		if(!v0.empty()&&(v1.empty()||v0.front()<v1.front()||k==0))
		{
			k++;
			c[i]=v0.front();
			v0.pop();
		}
		else k--,c[i]=v1.front(),v1.pop();
	}
	for(int i=n;i>=1;i--)
	{
		if(s[i]=='(') v0.push(i);
		else v1.push(i);
	}
	for(int i=1,k=0;i<=n;i++)
	{
		if(!v0.empty()&&(v1.empty()||v0.front()>v1.front()||k==0))
		{
			k++;
			d[i]=v0.front();
			v0.pop();
		}
		else k--,d[i]=v1.front(),v1.pop();
	}
	bool f=true;
//	for(int i=1;i<=n;i++) printf("%d ",c[i]);
//	printf("\n");
//	for(int i=1;i<=n;i++) printf("%d ",d[i]);
//	printf("\n");
	for(int i=1;i<=n&&f;i++) f&=a[i]==c[i];
	for(int i=1;i<=n&&f;i++) f&=b[i]==d[i];
	if(!f) puts("-1");
	else printf("%s\n",s+1);
	return 0;
}
/*
(
*/