AtCoder-abc350_f 题解

原题链接

题意简述

给定一个字符串 \(S\)，对于每个匹配的括号，将括号内的字符左右翻转并大小写反转，然后删除括号。输出最后的序列。

思路

本题为文艺平衡树的模板题。扫一遍字符串进行括号匹配，每次把最内层的括号进行操作。最后遍历一遍平衡树，将不为括号字符的字符输出。

FHQ_Treap 的常数太大，这里使用 Splay。

代码

#include<bits/stdc++.h>
#define UP(i,a,b) for(i=a;i<=(b);++i)
#define DN(i,a,b) for(i=a;i>=(b);--i)
#define up(i,a,b) for(i=a;i<(b);++i)
#define dn(i,a,b) for(i=a;i>(b);--i)
#define pa make_pair
typedef long long ll;
using namespace std;
void rdc(char &c){for(c=getchar();c==' '||c=='\r'||c=='\n';c=getchar());}

const int N=5e5+5;
char a[N];
int len,sta[N],*top;
/*sta和top用来括号匹配*/
struct node{
	bool lz,ch;
	/*lz为Lazy-Tag，ch为最后是否反转大小写*/
	int sz,vl;
	node *ls,*rs,*fa;
}t[N],*root,*tot;

void init_node(node *u,char c){
	u->lz=u->ch=false;
	u->sz=1;
	u->vl=c;
	u->ls=u->rs=u->fa=t;
}
void push_up(node *u){
	u->sz=u->ls->sz+u->rs->sz+1;
}
void tag(node *u){
	/*给子树打Lazy-Tag*/
	if(u!=t){
		swap(u->ls,u->rs);
		u->ch^=true;
		u->lz^=true;
	}
}
void push_down(node *u){
	/*下传标记*/
	if(u->lz){
		tag(u->ls);
		tag(u->rs);
		u->lz=false;
	}
}
bool ls(node *u){
	return u->fa->ls==u;
}
void rtt(node *u){
	/*Splay旋转*/
	node *f=u->fa,*g=f->fa;
	if(ls(u)){
		f->ls=u->rs;
		if(f->ls!=t){
			f->ls->fa=f;
		}
		u->rs=f;
	}else{
		f->rs=u->ls;
		if(f->rs!=t){
			f->rs->fa=f;
		}
		u->ls=f;
	}
	if(g!=t){
		ls(f)?g->ls=u:g->rs=u;
	}else{
		root=u;
	}
	f->fa=u;u->fa=g;
	push_up(f);push_up(u);
}
void splay(node *u,node *p){
	node *f,*g;
	while(u->fa!=p){
		f=u->fa;g=f->fa;
		if(g!=p){
			rtt(ls(u)^ls(f)?u:f);
		}
		rtt(u);
	}
}
node* fd(int k){
	node *u=root;
	/*找结点时要下传标记*/
	push_down(u);
	while(u->ls->sz+1!=k){
		if(k<u->ls->sz+1){
			u=u->ls;
		}else{
			k-=u->ls->sz+1;
			u=u->rs;
		}
		push_down(u);
	}
	return u;
}
node* build(node *f,int l,int r){
	/*对字符串的[l,r]建树，返回树根*/
	if(l>r){
		return t;
	}
	int mid=(l+r)>>1;
	node *u=++tot;
	init_node(u,a[mid]);
	u->fa=f;
	u->ls=build(u,l,mid-1);
	u->rs=build(u,mid+1,r);
	push_up(u);
	return u;
}
void rev(int l,int r){
	/*翻转并反转区间[l,r]*/
	node *x=fd(l),*y=fd(r+2);
	splay(x,t);
	splay(y,x);
	tag(y->ls);
}
void tra(node *u=root){
	/*遍历平衡树*/
	if(u!=t){
		push_down(u);
		tra(u->ls);
		if(u->vl!='('&&u->vl!=')'){
			/*不是括号时就输出*/
			if(u->ch){
				if(u->vl>='a'&&u->vl<='z'){
					u->vl-=32;
				}else{
					u->vl+=32;
				}
			}
			printf("%c",u->vl);
		}
		tra(u->rs);
	}
	if(u==root){
		printf("\n");
	}
}
void init(){
	init_node(t,'(');t->sz=0;
	init_node(t+1,'(');t[1].rs=t+2;t[1].sz=2;
	init_node(t+2,'(');t[2].fa=t+1;
	/*都初始化为'('，这样在遍历的时候就不输出多余字符了*/
	root=t+1;tot=t+2;top=sta;
}
int main(){
	int i;
	scanf("%s",a+1);
	len=strlen(a+1);
	init();
	t[2].ls=build(t+2,1,len);
	push_up(t+2);push_up(t+1);
	UP(i,1,len){
		if(a[i]=='('){
			++top;*top=i;
		}else if(a[i]==')'){
			/*括号匹配成功，进行翻转*/
			rev(*top,i);
			--top;
		}
	}
	tra();
	return 0;
}