我感觉自己代码的正确性好像没有保障,欢迎神仙们D我.(但是竟然AC了)

#include<map>
#include<set>
#include<queue>
#include<cmath>
#include<cstdio>
#include<vector>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#define lc (x<<1)
#define rc (x<<1|1)
#define gc getchar()//(p1==p2&&(p2=(p1=buf)+fread(buf,1,size,stdin),p1==p2)?EOF:*p1++)
#define mk make_pair
#define pi pair<int,int>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=1e6+10,size=1<<20;

//char buf[size],*p1=buf,*p2=buf;
template<class o> void qr(o &x) {
	char c=gc; x=0; int f=1;
	while(!isdigit(c)){if(c=='-')f=-1; c=gc;}
	while(isdigit(c)) x=x*10+c-'0',c=gc;
	x*=f;
}
template<class o> void qw(o x) {
	if(x/10) qw(x/10);
	putchar(x%10+'0');
}
template<class o> void pr1(o x) {
	if(x<0)x=-x,putchar('-');
	qw(x); putchar(' ');
}
template<class o> void pr2(o x) {
	if(x<0)x=-x,putchar('-');
	qw(x); puts("");
}

int n,ls,rs,flag;
char s[N];
vector<int> v[N];

int pos[N<<2],p,delta;

void upd(int &x,int y) {//y更新x的值 
	if(y==N-1) return ;
	if(x==N-1) x=y;
	else if(v[x].back()==0||-x+v[x].back()<-y+v[y].back()) x=y;
}

void bt(int x,int l,int r) {
	if(l==r) {
		if(v[l].size()) pos[x]=l;
		else pos[x]=N-1;
		return ;
	}
	int mid=(l+r)>>1;
	bt(lc,l,mid);
	bt(rc,mid+1,r);
	upd(pos[x]=pos[lc],pos[rc]);
}

void find(int x,int l,int r,int L,int R) {
	if(L<=l&&r<=R) {upd(p,pos[x]); return ;}
	int mid=(l+r)>>1;
	if(L<=mid) find(lc,l,mid,L,R);
	if(mid< R) find(rc,mid+1,r,L,R);
}

void del(int x,int l,int r) {
	if(l==r) {
		v[l].pop_back();
		if(v[l].size()) pos[x]=l;
		else pos[x]=N-1;
		return ;
	}
	int mid=(l+r)>>1;
	if(p<=mid) del(lc,l,mid);
	else del(rc,mid+1,r);
	upd(pos[x]=pos[lc],pos[rc]);
}

int main() {
	qr(n); 
	for(int i=1,l,r;i<=n;i++) {
		scanf("%s",s+1);l=r=0;
		for(int j=1;s[j];j++) 
			if(s[j]==')') {
				if(r) r--;
				else l++;
			}
			else r++;
		v[l].push_back(r);
		ls+=l; rs+=r;
		flag|=!l;
		flag|=(!r)*2;
	}
	if((ls^rs)||(flag^3)) puts("No"),exit(0);
	for(int i=0;i<=ls;i++) sort(v[i].begin(),v[i].end());
	bt(1,0,ls);
	for(int i=1,t=0;i<=n;i++) {
		p=N-1;
		find(1,0,ls,0,t);
		if(p==N-1) puts("No"),exit(0);
		t+=-p+v[p].back(); del(1,0,ls);
	}
	puts("Yes");
	return 0;
}

顺便宣传blog