arc120D - Bracket Score 2

D - Bracket Score 2

看了题解之后发现自己是弱智
如果能够猜到答案就是前n大-前n小，那么这题就解决了，直接用一个栈模拟匹配即可。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
using namespace std;
typedef double db;
typedef long long ll;
const int N=4e5+5;
const ll mo=1e9+7;
struct node{
	int x,id;
};
node a[N];
int n,b[N];
int top,s[N];
bool ans[N];
bool cmp(node a,node b){
	return a.x<b.x;
}
int main()
{
//	freopen("data.in","r",stdin);
	
	scanf("%d",&n);
	fo(i,1,2*n) {
		scanf("%d",&a[i].x);
		a[i].id=i;
	}
	
	sort(a+1,a+2*n+1,cmp);
	
	fo(i,1,2*n) b[a[i].id]=i;
	
	fo(i,1,2*n) {
		if (!top) s[++top]=b[i],ans[i]=0;
		else {
			if (s[top]>n && b[i]<=n) ans[i]=1,top--;
			else if (s[top]<=n && b[i]>n) ans[i]=1,top--;
			else s[++top]=b[i];
		}
	}
	
	fo(i,1,2*n) if (ans[i]) printf(")"); else printf("(");
	
	return 0;
}